isl_aff_align_divs: skip extension if local spaces are already the same
[isl.git] / isl_pw_templ.c
bloba9b4404ce722070859992fea7b1dae217e8beab5
1 /*
2 * Copyright 2010-2011 INRIA Saclay
3 * Copyright 2011 Sven Verdoolaege
4 * Copyright 2012-2014 Ecole Normale Superieure
6 * Use of this software is governed by the MIT license
8 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
9 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10 * 91893 Orsay, France
11 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
14 #include <isl/aff.h>
15 #include <isl_sort.h>
16 #include <isl_val_private.h>
18 #include <isl_pw_macro.h>
20 #ifdef HAS_TYPE
21 __isl_give PW *FN(PW,alloc_size)(__isl_take isl_space *dim,
22 enum isl_fold type, int n)
23 #else
24 __isl_give PW *FN(PW,alloc_size)(__isl_take isl_space *dim, int n)
25 #endif
27 isl_ctx *ctx;
28 struct PW *pw;
30 if (!dim)
31 return NULL;
32 ctx = isl_space_get_ctx(dim);
33 isl_assert(ctx, n >= 0, goto error);
34 pw = isl_alloc(ctx, struct PW,
35 sizeof(struct PW) + (n - 1) * sizeof(S(PW,piece)));
36 if (!pw)
37 goto error;
39 pw->ref = 1;
40 #ifdef HAS_TYPE
41 pw->type = type;
42 #endif
43 pw->size = n;
44 pw->n = 0;
45 pw->dim = dim;
46 return pw;
47 error:
48 isl_space_free(dim);
49 return NULL;
52 #ifdef HAS_TYPE
53 __isl_give PW *FN(PW,ZERO)(__isl_take isl_space *dim, enum isl_fold type)
55 return FN(PW,alloc_size)(dim, type, 0);
57 #else
58 __isl_give PW *FN(PW,ZERO)(__isl_take isl_space *dim)
60 return FN(PW,alloc_size)(dim, 0);
62 #endif
64 __isl_give PW *FN(PW,add_piece)(__isl_take PW *pw,
65 __isl_take isl_set *set, __isl_take EL *el)
67 isl_ctx *ctx;
68 isl_space *el_dim = NULL;
70 if (!pw || !set || !el)
71 goto error;
73 if (isl_set_plain_is_empty(set) || FN(EL,EL_IS_ZERO)(el)) {
74 isl_set_free(set);
75 FN(EL,free)(el);
76 return pw;
79 ctx = isl_set_get_ctx(set);
80 #ifdef HAS_TYPE
81 if (pw->type != el->type)
82 isl_die(ctx, isl_error_invalid, "fold types don't match",
83 goto error);
84 #endif
85 el_dim = FN(EL,get_space(el));
86 isl_assert(ctx, isl_space_is_equal(pw->dim, el_dim), goto error);
87 isl_assert(ctx, pw->n < pw->size, goto error);
89 pw->p[pw->n].set = set;
90 pw->p[pw->n].FIELD = el;
91 pw->n++;
93 isl_space_free(el_dim);
94 return pw;
95 error:
96 isl_space_free(el_dim);
97 FN(PW,free)(pw);
98 isl_set_free(set);
99 FN(EL,free)(el);
100 return NULL;
103 #ifdef HAS_TYPE
104 __isl_give PW *FN(PW,alloc)(enum isl_fold type,
105 __isl_take isl_set *set, __isl_take EL *el)
106 #else
107 __isl_give PW *FN(PW,alloc)(__isl_take isl_set *set, __isl_take EL *el)
108 #endif
110 PW *pw;
112 if (!set || !el)
113 goto error;
115 #ifdef HAS_TYPE
116 pw = FN(PW,alloc_size)(FN(EL,get_space)(el), type, 1);
117 #else
118 pw = FN(PW,alloc_size)(FN(EL,get_space)(el), 1);
119 #endif
121 return FN(PW,add_piece)(pw, set, el);
122 error:
123 isl_set_free(set);
124 FN(EL,free)(el);
125 return NULL;
128 __isl_give PW *FN(PW,dup)(__isl_keep PW *pw)
130 int i;
131 PW *dup;
133 if (!pw)
134 return NULL;
136 #ifdef HAS_TYPE
137 dup = FN(PW,alloc_size)(isl_space_copy(pw->dim), pw->type, pw->n);
138 #else
139 dup = FN(PW,alloc_size)(isl_space_copy(pw->dim), pw->n);
140 #endif
141 if (!dup)
142 return NULL;
144 for (i = 0; i < pw->n; ++i)
145 dup = FN(PW,add_piece)(dup, isl_set_copy(pw->p[i].set),
146 FN(EL,copy)(pw->p[i].FIELD));
148 return dup;
151 __isl_give PW *FN(PW,cow)(__isl_take PW *pw)
153 if (!pw)
154 return NULL;
156 if (pw->ref == 1)
157 return pw;
158 pw->ref--;
159 return FN(PW,dup)(pw);
162 __isl_give PW *FN(PW,copy)(__isl_keep PW *pw)
164 if (!pw)
165 return NULL;
167 pw->ref++;
168 return pw;
171 __isl_null PW *FN(PW,free)(__isl_take PW *pw)
173 int i;
175 if (!pw)
176 return NULL;
177 if (--pw->ref > 0)
178 return NULL;
180 for (i = 0; i < pw->n; ++i) {
181 isl_set_free(pw->p[i].set);
182 FN(EL,free)(pw->p[i].FIELD);
184 isl_space_free(pw->dim);
185 free(pw);
187 return NULL;
190 const char *FN(PW,get_dim_name)(__isl_keep PW *pw, enum isl_dim_type type,
191 unsigned pos)
193 return pw ? isl_space_get_dim_name(pw->dim, type, pos) : NULL;
196 isl_bool FN(PW,has_dim_id)(__isl_keep PW *pw, enum isl_dim_type type,
197 unsigned pos)
199 return pw ? isl_space_has_dim_id(pw->dim, type, pos) : isl_bool_error;
202 __isl_give isl_id *FN(PW,get_dim_id)(__isl_keep PW *pw, enum isl_dim_type type,
203 unsigned pos)
205 return pw ? isl_space_get_dim_id(pw->dim, type, pos) : NULL;
208 isl_bool FN(PW,has_tuple_name)(__isl_keep PW *pw, enum isl_dim_type type)
210 return pw ? isl_space_has_tuple_name(pw->dim, type) : isl_bool_error;
213 const char *FN(PW,get_tuple_name)(__isl_keep PW *pw, enum isl_dim_type type)
215 return pw ? isl_space_get_tuple_name(pw->dim, type) : NULL;
218 isl_bool FN(PW,has_tuple_id)(__isl_keep PW *pw, enum isl_dim_type type)
220 return pw ? isl_space_has_tuple_id(pw->dim, type) : isl_bool_error;
223 __isl_give isl_id *FN(PW,get_tuple_id)(__isl_keep PW *pw, enum isl_dim_type type)
225 return pw ? isl_space_get_tuple_id(pw->dim, type) : NULL;
228 isl_bool FN(PW,IS_ZERO)(__isl_keep PW *pw)
230 if (!pw)
231 return isl_bool_error;
233 return pw->n == 0;
236 #ifndef NO_REALIGN
237 __isl_give PW *FN(PW,realign_domain)(__isl_take PW *pw,
238 __isl_take isl_reordering *exp)
240 int i;
242 pw = FN(PW,cow)(pw);
243 if (!pw || !exp)
244 goto error;
246 for (i = 0; i < pw->n; ++i) {
247 pw->p[i].set = isl_set_realign(pw->p[i].set,
248 isl_reordering_copy(exp));
249 if (!pw->p[i].set)
250 goto error;
251 pw->p[i].FIELD = FN(EL,realign_domain)(pw->p[i].FIELD,
252 isl_reordering_copy(exp));
253 if (!pw->p[i].FIELD)
254 goto error;
257 pw = FN(PW,reset_domain_space)(pw, isl_space_copy(exp->dim));
259 isl_reordering_free(exp);
260 return pw;
261 error:
262 isl_reordering_free(exp);
263 FN(PW,free)(pw);
264 return NULL;
267 /* Align the parameters of "pw" to those of "model".
269 __isl_give PW *FN(PW,align_params)(__isl_take PW *pw, __isl_take isl_space *model)
271 isl_ctx *ctx;
273 if (!pw || !model)
274 goto error;
276 ctx = isl_space_get_ctx(model);
277 if (!isl_space_has_named_params(model))
278 isl_die(ctx, isl_error_invalid,
279 "model has unnamed parameters", goto error);
280 if (!isl_space_has_named_params(pw->dim))
281 isl_die(ctx, isl_error_invalid,
282 "input has unnamed parameters", goto error);
283 if (!isl_space_match(pw->dim, isl_dim_param, model, isl_dim_param)) {
284 isl_reordering *exp;
286 model = isl_space_drop_dims(model, isl_dim_in,
287 0, isl_space_dim(model, isl_dim_in));
288 model = isl_space_drop_dims(model, isl_dim_out,
289 0, isl_space_dim(model, isl_dim_out));
290 exp = isl_parameter_alignment_reordering(pw->dim, model);
291 exp = isl_reordering_extend_space(exp,
292 FN(PW,get_domain_space)(pw));
293 pw = FN(PW,realign_domain)(pw, exp);
296 isl_space_free(model);
297 return pw;
298 error:
299 isl_space_free(model);
300 FN(PW,free)(pw);
301 return NULL;
304 static __isl_give PW *FN(PW,align_params_pw_pw_and)(__isl_take PW *pw1,
305 __isl_take PW *pw2,
306 __isl_give PW *(*fn)(__isl_take PW *pw1, __isl_take PW *pw2))
308 isl_ctx *ctx;
310 if (!pw1 || !pw2)
311 goto error;
312 if (isl_space_match(pw1->dim, isl_dim_param, pw2->dim, isl_dim_param))
313 return fn(pw1, pw2);
314 ctx = FN(PW,get_ctx)(pw1);
315 if (!isl_space_has_named_params(pw1->dim) ||
316 !isl_space_has_named_params(pw2->dim))
317 isl_die(ctx, isl_error_invalid,
318 "unaligned unnamed parameters", goto error);
319 pw1 = FN(PW,align_params)(pw1, FN(PW,get_space)(pw2));
320 pw2 = FN(PW,align_params)(pw2, FN(PW,get_space)(pw1));
321 return fn(pw1, pw2);
322 error:
323 FN(PW,free)(pw1);
324 FN(PW,free)(pw2);
325 return NULL;
328 static __isl_give PW *FN(PW,align_params_pw_set_and)(__isl_take PW *pw,
329 __isl_take isl_set *set,
330 __isl_give PW *(*fn)(__isl_take PW *pw, __isl_take isl_set *set))
332 isl_ctx *ctx;
334 if (!pw || !set)
335 goto error;
336 if (isl_space_match(pw->dim, isl_dim_param, set->dim, isl_dim_param))
337 return fn(pw, set);
338 ctx = FN(PW,get_ctx)(pw);
339 if (!isl_space_has_named_params(pw->dim) ||
340 !isl_space_has_named_params(set->dim))
341 isl_die(ctx, isl_error_invalid,
342 "unaligned unnamed parameters", goto error);
343 pw = FN(PW,align_params)(pw, isl_set_get_space(set));
344 set = isl_set_align_params(set, FN(PW,get_space)(pw));
345 return fn(pw, set);
346 error:
347 FN(PW,free)(pw);
348 isl_set_free(set);
349 return NULL;
351 #endif
353 static __isl_give PW *FN(PW,union_add_aligned)(__isl_take PW *pw1,
354 __isl_take PW *pw2)
356 int i, j, n;
357 struct PW *res;
358 isl_ctx *ctx;
359 isl_set *set;
361 if (!pw1 || !pw2)
362 goto error;
364 ctx = isl_space_get_ctx(pw1->dim);
365 #ifdef HAS_TYPE
366 if (pw1->type != pw2->type)
367 isl_die(ctx, isl_error_invalid,
368 "fold types don't match", goto error);
369 #endif
370 isl_assert(ctx, isl_space_is_equal(pw1->dim, pw2->dim), goto error);
372 if (FN(PW,IS_ZERO)(pw1)) {
373 FN(PW,free)(pw1);
374 return pw2;
377 if (FN(PW,IS_ZERO)(pw2)) {
378 FN(PW,free)(pw2);
379 return pw1;
382 n = (pw1->n + 1) * (pw2->n + 1);
383 #ifdef HAS_TYPE
384 res = FN(PW,alloc_size)(isl_space_copy(pw1->dim), pw1->type, n);
385 #else
386 res = FN(PW,alloc_size)(isl_space_copy(pw1->dim), n);
387 #endif
389 for (i = 0; i < pw1->n; ++i) {
390 set = isl_set_copy(pw1->p[i].set);
391 for (j = 0; j < pw2->n; ++j) {
392 struct isl_set *common;
393 EL *sum;
394 common = isl_set_intersect(isl_set_copy(pw1->p[i].set),
395 isl_set_copy(pw2->p[j].set));
396 if (isl_set_plain_is_empty(common)) {
397 isl_set_free(common);
398 continue;
400 set = isl_set_subtract(set,
401 isl_set_copy(pw2->p[j].set));
403 sum = FN(EL,add_on_domain)(common,
404 FN(EL,copy)(pw1->p[i].FIELD),
405 FN(EL,copy)(pw2->p[j].FIELD));
407 res = FN(PW,add_piece)(res, common, sum);
409 res = FN(PW,add_piece)(res, set, FN(EL,copy)(pw1->p[i].FIELD));
412 for (j = 0; j < pw2->n; ++j) {
413 set = isl_set_copy(pw2->p[j].set);
414 for (i = 0; i < pw1->n; ++i)
415 set = isl_set_subtract(set,
416 isl_set_copy(pw1->p[i].set));
417 res = FN(PW,add_piece)(res, set, FN(EL,copy)(pw2->p[j].FIELD));
420 FN(PW,free)(pw1);
421 FN(PW,free)(pw2);
423 return res;
424 error:
425 FN(PW,free)(pw1);
426 FN(PW,free)(pw2);
427 return NULL;
430 /* Private version of "union_add". For isl_pw_qpolynomial and
431 * isl_pw_qpolynomial_fold, we prefer to simply call it "add".
433 static __isl_give PW *FN(PW,union_add_)(__isl_take PW *pw1, __isl_take PW *pw2)
435 return FN(PW,align_params_pw_pw_and)(pw1, pw2,
436 &FN(PW,union_add_aligned));
439 /* Make sure "pw" has room for at least "n" more pieces.
441 * If there is only one reference to pw, we extend it in place.
442 * Otherwise, we create a new PW and copy the pieces.
444 static __isl_give PW *FN(PW,grow)(__isl_take PW *pw, int n)
446 int i;
447 isl_ctx *ctx;
448 PW *res;
450 if (!pw)
451 return NULL;
452 if (pw->n + n <= pw->size)
453 return pw;
454 ctx = FN(PW,get_ctx)(pw);
455 n += pw->n;
456 if (pw->ref == 1) {
457 res = isl_realloc(ctx, pw, struct PW,
458 sizeof(struct PW) + (n - 1) * sizeof(S(PW,piece)));
459 if (!res)
460 return FN(PW,free)(pw);
461 res->size = n;
462 return res;
464 #ifdef HAS_TYPE
465 res = FN(PW,alloc_size)(isl_space_copy(pw->dim), pw->type, n);
466 #else
467 res = FN(PW,alloc_size)(isl_space_copy(pw->dim), n);
468 #endif
469 if (!res)
470 return FN(PW,free)(pw);
471 for (i = 0; i < pw->n; ++i)
472 res = FN(PW,add_piece)(res, isl_set_copy(pw->p[i].set),
473 FN(EL,copy)(pw->p[i].FIELD));
474 FN(PW,free)(pw);
475 return res;
478 static __isl_give PW *FN(PW,add_disjoint_aligned)(__isl_take PW *pw1,
479 __isl_take PW *pw2)
481 int i;
482 isl_ctx *ctx;
484 if (!pw1 || !pw2)
485 goto error;
487 if (pw1->size < pw1->n + pw2->n && pw1->n < pw2->n)
488 return FN(PW,add_disjoint_aligned)(pw2, pw1);
490 ctx = isl_space_get_ctx(pw1->dim);
491 #ifdef HAS_TYPE
492 if (pw1->type != pw2->type)
493 isl_die(ctx, isl_error_invalid,
494 "fold types don't match", goto error);
495 #endif
496 isl_assert(ctx, isl_space_is_equal(pw1->dim, pw2->dim), goto error);
498 if (FN(PW,IS_ZERO)(pw1)) {
499 FN(PW,free)(pw1);
500 return pw2;
503 if (FN(PW,IS_ZERO)(pw2)) {
504 FN(PW,free)(pw2);
505 return pw1;
508 pw1 = FN(PW,grow)(pw1, pw2->n);
509 if (!pw1)
510 goto error;
512 for (i = 0; i < pw2->n; ++i)
513 pw1 = FN(PW,add_piece)(pw1,
514 isl_set_copy(pw2->p[i].set),
515 FN(EL,copy)(pw2->p[i].FIELD));
517 FN(PW,free)(pw2);
519 return pw1;
520 error:
521 FN(PW,free)(pw1);
522 FN(PW,free)(pw2);
523 return NULL;
526 __isl_give PW *FN(PW,add_disjoint)(__isl_take PW *pw1, __isl_take PW *pw2)
528 return FN(PW,align_params_pw_pw_and)(pw1, pw2,
529 &FN(PW,add_disjoint_aligned));
532 /* This function is currently only used from isl_aff.c
534 static __isl_give PW *FN(PW,on_shared_domain_in)(__isl_take PW *pw1,
535 __isl_take PW *pw2, __isl_take isl_space *space,
536 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))
537 __attribute__ ((unused));
539 /* Apply "fn" to pairs of elements from pw1 and pw2 on shared domains.
540 * The result of "fn" (and therefore also of this function) lives in "space".
542 static __isl_give PW *FN(PW,on_shared_domain_in)(__isl_take PW *pw1,
543 __isl_take PW *pw2, __isl_take isl_space *space,
544 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))
546 int i, j, n;
547 PW *res = NULL;
549 if (!pw1 || !pw2)
550 goto error;
552 n = pw1->n * pw2->n;
553 #ifdef HAS_TYPE
554 res = FN(PW,alloc_size)(isl_space_copy(space), pw1->type, n);
555 #else
556 res = FN(PW,alloc_size)(isl_space_copy(space), n);
557 #endif
559 for (i = 0; i < pw1->n; ++i) {
560 for (j = 0; j < pw2->n; ++j) {
561 isl_set *common;
562 EL *res_ij;
563 int empty;
565 common = isl_set_intersect(
566 isl_set_copy(pw1->p[i].set),
567 isl_set_copy(pw2->p[j].set));
568 empty = isl_set_plain_is_empty(common);
569 if (empty < 0 || empty) {
570 isl_set_free(common);
571 if (empty < 0)
572 goto error;
573 continue;
576 res_ij = fn(FN(EL,copy)(pw1->p[i].FIELD),
577 FN(EL,copy)(pw2->p[j].FIELD));
578 res_ij = FN(EL,gist)(res_ij, isl_set_copy(common));
580 res = FN(PW,add_piece)(res, common, res_ij);
584 isl_space_free(space);
585 FN(PW,free)(pw1);
586 FN(PW,free)(pw2);
587 return res;
588 error:
589 isl_space_free(space);
590 FN(PW,free)(pw1);
591 FN(PW,free)(pw2);
592 FN(PW,free)(res);
593 return NULL;
596 /* This function is currently only used from isl_aff.c
598 static __isl_give PW *FN(PW,on_shared_domain)(__isl_take PW *pw1,
599 __isl_take PW *pw2,
600 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))
601 __attribute__ ((unused));
603 /* Apply "fn" to pairs of elements from pw1 and pw2 on shared domains.
604 * The result of "fn" is assumed to live in the same space as "pw1" and "pw2".
606 static __isl_give PW *FN(PW,on_shared_domain)(__isl_take PW *pw1,
607 __isl_take PW *pw2,
608 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))
610 isl_space *space;
612 if (!pw1 || !pw2)
613 goto error;
615 space = isl_space_copy(pw1->dim);
616 return FN(PW,on_shared_domain_in)(pw1, pw2, space, fn);
617 error:
618 FN(PW,free)(pw1);
619 FN(PW,free)(pw2);
620 return NULL;
623 #ifndef NO_NEG
624 __isl_give PW *FN(PW,neg)(__isl_take PW *pw)
626 int i;
628 if (!pw)
629 return NULL;
631 if (FN(PW,IS_ZERO)(pw))
632 return pw;
634 pw = FN(PW,cow)(pw);
635 if (!pw)
636 return NULL;
638 for (i = 0; i < pw->n; ++i) {
639 pw->p[i].FIELD = FN(EL,neg)(pw->p[i].FIELD);
640 if (!pw->p[i].FIELD)
641 return FN(PW,free)(pw);
644 return pw;
646 #endif
648 #ifndef NO_SUB
649 __isl_give PW *FN(PW,sub)(__isl_take PW *pw1, __isl_take PW *pw2)
651 return FN(PW,add)(pw1, FN(PW,neg)(pw2));
653 #endif
655 #ifndef NO_EVAL
656 __isl_give isl_val *FN(PW,eval)(__isl_take PW *pw, __isl_take isl_point *pnt)
658 int i;
659 int found = 0;
660 isl_ctx *ctx;
661 isl_space *pnt_dim = NULL;
662 isl_val *v;
664 if (!pw || !pnt)
665 goto error;
666 ctx = isl_point_get_ctx(pnt);
667 pnt_dim = isl_point_get_space(pnt);
668 isl_assert(ctx, isl_space_is_domain_internal(pnt_dim, pw->dim),
669 goto error);
671 for (i = 0; i < pw->n; ++i) {
672 found = isl_set_contains_point(pw->p[i].set, pnt);
673 if (found < 0)
674 goto error;
675 if (found)
676 break;
678 if (found)
679 v = FN(EL,eval)(FN(EL,copy)(pw->p[i].FIELD),
680 isl_point_copy(pnt));
681 else
682 v = isl_val_zero(ctx);
683 FN(PW,free)(pw);
684 isl_space_free(pnt_dim);
685 isl_point_free(pnt);
686 return v;
687 error:
688 FN(PW,free)(pw);
689 isl_space_free(pnt_dim);
690 isl_point_free(pnt);
691 return NULL;
693 #endif
695 /* Return the parameter domain of "pw".
697 __isl_give isl_set *FN(PW,params)(__isl_take PW *pw)
699 return isl_set_params(FN(PW,domain)(pw));
702 __isl_give isl_set *FN(PW,domain)(__isl_take PW *pw)
704 int i;
705 isl_set *dom;
707 if (!pw)
708 return NULL;
710 dom = isl_set_empty(FN(PW,get_domain_space)(pw));
711 for (i = 0; i < pw->n; ++i)
712 dom = isl_set_union_disjoint(dom, isl_set_copy(pw->p[i].set));
714 FN(PW,free)(pw);
716 return dom;
719 /* Exploit the equalities in the domain of piece "i" of "pw"
720 * to simplify the associated function.
721 * If the domain of piece "i" is empty, then remove it entirely,
722 * replacing it with the final piece.
724 static int FN(PW,exploit_equalities_and_remove_if_empty)(__isl_keep PW *pw,
725 int i)
727 isl_basic_set *aff;
728 int empty = isl_set_plain_is_empty(pw->p[i].set);
730 if (empty < 0)
731 return -1;
732 if (empty) {
733 isl_set_free(pw->p[i].set);
734 FN(EL,free)(pw->p[i].FIELD);
735 if (i != pw->n - 1)
736 pw->p[i] = pw->p[pw->n - 1];
737 pw->n--;
739 return 0;
742 aff = isl_set_affine_hull(isl_set_copy(pw->p[i].set));
743 pw->p[i].FIELD = FN(EL,substitute_equalities)(pw->p[i].FIELD, aff);
744 if (!pw->p[i].FIELD)
745 return -1;
747 return 0;
750 /* Convert a piecewise expression defined over a parameter domain
751 * into one that is defined over a zero-dimensional set.
753 __isl_give PW *FN(PW,from_range)(__isl_take PW *pw)
755 isl_space *space;
757 if (!pw)
758 return NULL;
759 if (!isl_space_is_set(pw->dim))
760 isl_die(FN(PW,get_ctx)(pw), isl_error_invalid,
761 "not living in a set space", return FN(PW,free)(pw));
763 space = FN(PW,get_space)(pw);
764 space = isl_space_from_range(space);
765 pw = FN(PW,reset_space)(pw, space);
767 return pw;
770 /* Fix the value of the given parameter or domain dimension of "pw"
771 * to be equal to "value".
773 __isl_give PW *FN(PW,fix_si)(__isl_take PW *pw, enum isl_dim_type type,
774 unsigned pos, int value)
776 int i;
778 if (!pw)
779 return NULL;
781 if (type == isl_dim_out)
782 isl_die(FN(PW,get_ctx)(pw), isl_error_invalid,
783 "cannot fix output dimension", return FN(PW,free)(pw));
785 if (pw->n == 0)
786 return pw;
788 if (type == isl_dim_in)
789 type = isl_dim_set;
791 pw = FN(PW,cow)(pw);
792 if (!pw)
793 return FN(PW,free)(pw);
795 for (i = pw->n - 1; i >= 0; --i) {
796 pw->p[i].set = isl_set_fix_si(pw->p[i].set, type, pos, value);
797 if (FN(PW,exploit_equalities_and_remove_if_empty)(pw, i) < 0)
798 return FN(PW,free)(pw);
801 return pw;
804 /* Restrict the domain of "pw" by combining each cell
805 * with "set" through a call to "fn", where "fn" may be
806 * isl_set_intersect, isl_set_intersect_params or isl_set_subtract.
808 static __isl_give PW *FN(PW,restrict_domain_aligned)(__isl_take PW *pw,
809 __isl_take isl_set *set,
810 __isl_give isl_set *(*fn)(__isl_take isl_set *set1,
811 __isl_take isl_set *set2))
813 int i;
815 if (!pw || !set)
816 goto error;
818 if (pw->n == 0) {
819 isl_set_free(set);
820 return pw;
823 pw = FN(PW,cow)(pw);
824 if (!pw)
825 goto error;
827 for (i = pw->n - 1; i >= 0; --i) {
828 pw->p[i].set = fn(pw->p[i].set, isl_set_copy(set));
829 if (FN(PW,exploit_equalities_and_remove_if_empty)(pw, i) < 0)
830 goto error;
833 isl_set_free(set);
834 return pw;
835 error:
836 isl_set_free(set);
837 FN(PW,free)(pw);
838 return NULL;
841 static __isl_give PW *FN(PW,intersect_domain_aligned)(__isl_take PW *pw,
842 __isl_take isl_set *set)
844 return FN(PW,restrict_domain_aligned)(pw, set, &isl_set_intersect);
847 __isl_give PW *FN(PW,intersect_domain)(__isl_take PW *pw,
848 __isl_take isl_set *context)
850 return FN(PW,align_params_pw_set_and)(pw, context,
851 &FN(PW,intersect_domain_aligned));
854 static __isl_give PW *FN(PW,intersect_params_aligned)(__isl_take PW *pw,
855 __isl_take isl_set *set)
857 return FN(PW,restrict_domain_aligned)(pw, set,
858 &isl_set_intersect_params);
861 /* Intersect the domain of "pw" with the parameter domain "context".
863 __isl_give PW *FN(PW,intersect_params)(__isl_take PW *pw,
864 __isl_take isl_set *context)
866 return FN(PW,align_params_pw_set_and)(pw, context,
867 &FN(PW,intersect_params_aligned));
870 /* Subtract "domain' from the domain of "pw", assuming their
871 * parameters have been aligned.
873 static __isl_give PW *FN(PW,subtract_domain_aligned)(__isl_take PW *pw,
874 __isl_take isl_set *domain)
876 return FN(PW,restrict_domain_aligned)(pw, domain, &isl_set_subtract);
879 /* Subtract "domain' from the domain of "pw".
881 __isl_give PW *FN(PW,subtract_domain)(__isl_take PW *pw,
882 __isl_take isl_set *domain)
884 return FN(PW,align_params_pw_set_and)(pw, domain,
885 &FN(PW,subtract_domain_aligned));
888 /* Compute the gist of "pw" with respect to the domain constraints
889 * of "context" for the case where the domain of the last element
890 * of "pw" is equal to "context".
891 * Call "fn_el" to compute the gist of this element, replace
892 * its domain by the universe and drop all other elements
893 * as their domains are necessarily disjoint from "context".
895 static __isl_give PW *FN(PW,gist_last)(__isl_take PW *pw,
896 __isl_take isl_set *context,
897 __isl_give EL *(*fn_el)(__isl_take EL *el, __isl_take isl_set *set))
899 int i;
900 isl_space *space;
902 for (i = 0; i < pw->n - 1; ++i) {
903 isl_set_free(pw->p[i].set);
904 FN(EL,free)(pw->p[i].FIELD);
906 pw->p[0].FIELD = pw->p[pw->n - 1].FIELD;
907 pw->p[0].set = pw->p[pw->n - 1].set;
908 pw->n = 1;
910 space = isl_set_get_space(context);
911 pw->p[0].FIELD = fn_el(pw->p[0].FIELD, context);
912 context = isl_set_universe(space);
913 isl_set_free(pw->p[0].set);
914 pw->p[0].set = context;
916 if (!pw->p[0].FIELD || !pw->p[0].set)
917 return FN(PW,free)(pw);
919 return pw;
922 /* Compute the gist of "pw" with respect to the domain constraints
923 * of "context". Call "fn_el" to compute the gist of the elements
924 * and "fn_dom" to compute the gist of the domains.
926 * If the piecewise expression is empty or the context is the universe,
927 * then nothing can be simplified.
929 static __isl_give PW *FN(PW,gist_aligned)(__isl_take PW *pw,
930 __isl_take isl_set *context,
931 __isl_give EL *(*fn_el)(__isl_take EL *el,
932 __isl_take isl_set *set),
933 __isl_give isl_set *(*fn_dom)(__isl_take isl_set *set,
934 __isl_take isl_basic_set *bset))
936 int i;
937 int is_universe;
938 isl_basic_set *hull = NULL;
940 if (!pw || !context)
941 goto error;
943 if (pw->n == 0) {
944 isl_set_free(context);
945 return pw;
948 is_universe = isl_set_plain_is_universe(context);
949 if (is_universe < 0)
950 goto error;
951 if (is_universe) {
952 isl_set_free(context);
953 return pw;
956 if (!isl_space_match(pw->dim, isl_dim_param,
957 context->dim, isl_dim_param)) {
958 pw = FN(PW,align_params)(pw, isl_set_get_space(context));
959 context = isl_set_align_params(context, FN(PW,get_space)(pw));
962 pw = FN(PW,cow)(pw);
963 if (!pw)
964 goto error;
966 if (pw->n == 1) {
967 int equal;
969 equal = isl_set_plain_is_equal(pw->p[0].set, context);
970 if (equal < 0)
971 goto error;
972 if (equal)
973 return FN(PW,gist_last)(pw, context, fn_el);
976 context = isl_set_compute_divs(context);
977 hull = isl_set_simple_hull(isl_set_copy(context));
979 for (i = pw->n - 1; i >= 0; --i) {
980 isl_set *set_i;
981 int empty;
983 if (i == pw->n - 1) {
984 int equal;
985 equal = isl_set_plain_is_equal(pw->p[i].set, context);
986 if (equal < 0)
987 goto error;
988 if (equal) {
989 isl_basic_set_free(hull);
990 return FN(PW,gist_last)(pw, context, fn_el);
993 set_i = isl_set_intersect(isl_set_copy(pw->p[i].set),
994 isl_set_copy(context));
995 empty = isl_set_plain_is_empty(set_i);
996 pw->p[i].FIELD = fn_el(pw->p[i].FIELD, set_i);
997 pw->p[i].set = fn_dom(pw->p[i].set, isl_basic_set_copy(hull));
998 if (empty < 0 || !pw->p[i].FIELD || !pw->p[i].set)
999 goto error;
1000 if (empty) {
1001 isl_set_free(pw->p[i].set);
1002 FN(EL,free)(pw->p[i].FIELD);
1003 if (i != pw->n - 1)
1004 pw->p[i] = pw->p[pw->n - 1];
1005 pw->n--;
1009 isl_basic_set_free(hull);
1010 isl_set_free(context);
1012 return pw;
1013 error:
1014 FN(PW,free)(pw);
1015 isl_basic_set_free(hull);
1016 isl_set_free(context);
1017 return NULL;
1020 static __isl_give PW *FN(PW,gist_domain_aligned)(__isl_take PW *pw,
1021 __isl_take isl_set *set)
1023 return FN(PW,gist_aligned)(pw, set, &FN(EL,gist),
1024 &isl_set_gist_basic_set);
1027 __isl_give PW *FN(PW,gist)(__isl_take PW *pw, __isl_take isl_set *context)
1029 return FN(PW,align_params_pw_set_and)(pw, context,
1030 &FN(PW,gist_domain_aligned));
1033 static __isl_give PW *FN(PW,gist_params_aligned)(__isl_take PW *pw,
1034 __isl_take isl_set *set)
1036 return FN(PW,gist_aligned)(pw, set, &FN(EL,gist_params),
1037 &isl_set_gist_params_basic_set);
1040 __isl_give PW *FN(PW,gist_params)(__isl_take PW *pw,
1041 __isl_take isl_set *context)
1043 return FN(PW,align_params_pw_set_and)(pw, context,
1044 &FN(PW,gist_params_aligned));
1047 /* Return -1 if the piece "p1" should be sorted before "p2"
1048 * and 1 if it should be sorted after "p2".
1049 * Return 0 if they do not need to be sorted in a specific order.
1051 * The two pieces are compared on the basis of their function value expressions.
1053 static int FN(PW,sort_field_cmp)(const void *p1, const void *p2, void *arg)
1055 struct FN(PW,piece) const *pc1 = p1;
1056 struct FN(PW,piece) const *pc2 = p2;
1058 return FN(EL,plain_cmp)(pc1->FIELD, pc2->FIELD);
1061 /* Sort the pieces of "pw" according to their function value
1062 * expressions and then combine pairs of adjacent pieces with
1063 * the same such expression.
1065 * The sorting is performed in place because it does not
1066 * change the meaning of "pw", but care needs to be
1067 * taken not to change any possible other copies of "pw"
1068 * in case anything goes wrong.
1070 __isl_give PW *FN(PW,sort)(__isl_take PW *pw)
1072 int i, j;
1073 isl_set *set;
1075 if (!pw)
1076 return NULL;
1077 if (pw->n <= 1)
1078 return pw;
1079 if (isl_sort(pw->p, pw->n, sizeof(pw->p[0]),
1080 &FN(PW,sort_field_cmp), NULL) < 0)
1081 return FN(PW,free)(pw);
1082 for (i = pw->n - 1; i >= 1; --i) {
1083 if (!FN(EL,plain_is_equal)(pw->p[i - 1].FIELD, pw->p[i].FIELD))
1084 continue;
1085 set = isl_set_union(isl_set_copy(pw->p[i - 1].set),
1086 isl_set_copy(pw->p[i].set));
1087 if (!set)
1088 return FN(PW,free)(pw);
1089 isl_set_free(pw->p[i].set);
1090 FN(EL,free)(pw->p[i].FIELD);
1091 isl_set_free(pw->p[i - 1].set);
1092 pw->p[i - 1].set = set;
1093 for (j = i + 1; j < pw->n; ++j)
1094 pw->p[j - 1] = pw->p[j];
1095 pw->n--;
1098 return pw;
1101 /* Coalesce the domains of "pw".
1103 * Prior to the actual coalescing, first sort the pieces such that
1104 * pieces with the same function value expression are combined
1105 * into a single piece, the combined domain of which can then
1106 * be coalesced.
1108 __isl_give PW *FN(PW,coalesce)(__isl_take PW *pw)
1110 int i;
1112 pw = FN(PW,sort)(pw);
1113 if (!pw)
1114 return NULL;
1116 for (i = 0; i < pw->n; ++i) {
1117 pw->p[i].set = isl_set_coalesce(pw->p[i].set);
1118 if (!pw->p[i].set)
1119 goto error;
1122 return pw;
1123 error:
1124 FN(PW,free)(pw);
1125 return NULL;
1128 isl_ctx *FN(PW,get_ctx)(__isl_keep PW *pw)
1130 return pw ? isl_space_get_ctx(pw->dim) : NULL;
1133 #ifndef NO_INVOLVES_DIMS
1134 isl_bool FN(PW,involves_dims)(__isl_keep PW *pw, enum isl_dim_type type,
1135 unsigned first, unsigned n)
1137 int i;
1138 enum isl_dim_type set_type;
1140 if (!pw)
1141 return isl_bool_error;
1142 if (pw->n == 0 || n == 0)
1143 return isl_bool_false;
1145 set_type = type == isl_dim_in ? isl_dim_set : type;
1147 for (i = 0; i < pw->n; ++i) {
1148 isl_bool involves = FN(EL,involves_dims)(pw->p[i].FIELD,
1149 type, first, n);
1150 if (involves < 0 || involves)
1151 return involves;
1152 involves = isl_set_involves_dims(pw->p[i].set,
1153 set_type, first, n);
1154 if (involves < 0 || involves)
1155 return involves;
1157 return isl_bool_false;
1159 #endif
1161 __isl_give PW *FN(PW,set_dim_name)(__isl_take PW *pw,
1162 enum isl_dim_type type, unsigned pos, const char *s)
1164 int i;
1165 enum isl_dim_type set_type;
1167 pw = FN(PW,cow)(pw);
1168 if (!pw)
1169 return NULL;
1171 set_type = type == isl_dim_in ? isl_dim_set : type;
1173 pw->dim = isl_space_set_dim_name(pw->dim, type, pos, s);
1174 if (!pw->dim)
1175 goto error;
1177 for (i = 0; i < pw->n; ++i) {
1178 pw->p[i].set = isl_set_set_dim_name(pw->p[i].set,
1179 set_type, pos, s);
1180 if (!pw->p[i].set)
1181 goto error;
1182 pw->p[i].FIELD = FN(EL,set_dim_name)(pw->p[i].FIELD, type, pos, s);
1183 if (!pw->p[i].FIELD)
1184 goto error;
1187 return pw;
1188 error:
1189 FN(PW,free)(pw);
1190 return NULL;
1193 #ifndef NO_DROP_DIMS
1194 __isl_give PW *FN(PW,drop_dims)(__isl_take PW *pw,
1195 enum isl_dim_type type, unsigned first, unsigned n)
1197 int i;
1198 enum isl_dim_type set_type;
1200 if (!pw)
1201 return NULL;
1202 if (n == 0 && !isl_space_get_tuple_name(pw->dim, type))
1203 return pw;
1205 set_type = type == isl_dim_in ? isl_dim_set : type;
1207 pw = FN(PW,cow)(pw);
1208 if (!pw)
1209 return NULL;
1210 pw->dim = isl_space_drop_dims(pw->dim, type, first, n);
1211 if (!pw->dim)
1212 goto error;
1213 for (i = 0; i < pw->n; ++i) {
1214 pw->p[i].FIELD = FN(EL,drop_dims)(pw->p[i].FIELD, type, first, n);
1215 if (!pw->p[i].FIELD)
1216 goto error;
1217 if (type == isl_dim_out)
1218 continue;
1219 pw->p[i].set = isl_set_drop(pw->p[i].set, set_type, first, n);
1220 if (!pw->p[i].set)
1221 goto error;
1224 return pw;
1225 error:
1226 FN(PW,free)(pw);
1227 return NULL;
1230 /* This function is very similar to drop_dims.
1231 * The only difference is that the cells may still involve
1232 * the specified dimensions. They are removed using
1233 * isl_set_project_out instead of isl_set_drop.
1235 __isl_give PW *FN(PW,project_out)(__isl_take PW *pw,
1236 enum isl_dim_type type, unsigned first, unsigned n)
1238 int i;
1239 enum isl_dim_type set_type;
1241 if (!pw)
1242 return NULL;
1243 if (n == 0 && !isl_space_get_tuple_name(pw->dim, type))
1244 return pw;
1246 set_type = type == isl_dim_in ? isl_dim_set : type;
1248 pw = FN(PW,cow)(pw);
1249 if (!pw)
1250 return NULL;
1251 pw->dim = isl_space_drop_dims(pw->dim, type, first, n);
1252 if (!pw->dim)
1253 goto error;
1254 for (i = 0; i < pw->n; ++i) {
1255 pw->p[i].set = isl_set_project_out(pw->p[i].set,
1256 set_type, first, n);
1257 if (!pw->p[i].set)
1258 goto error;
1259 pw->p[i].FIELD = FN(EL,drop_dims)(pw->p[i].FIELD, type, first, n);
1260 if (!pw->p[i].FIELD)
1261 goto error;
1264 return pw;
1265 error:
1266 FN(PW,free)(pw);
1267 return NULL;
1270 /* Project the domain of pw onto its parameter space.
1272 __isl_give PW *FN(PW,project_domain_on_params)(__isl_take PW *pw)
1274 isl_space *space;
1275 unsigned n;
1277 n = FN(PW,dim)(pw, isl_dim_in);
1278 pw = FN(PW,project_out)(pw, isl_dim_in, 0, n);
1279 space = FN(PW,get_domain_space)(pw);
1280 space = isl_space_params(space);
1281 pw = FN(PW,reset_domain_space)(pw, space);
1282 return pw;
1284 #endif
1286 #ifndef NO_INSERT_DIMS
1287 __isl_give PW *FN(PW,insert_dims)(__isl_take PW *pw, enum isl_dim_type type,
1288 unsigned first, unsigned n)
1290 int i;
1291 enum isl_dim_type set_type;
1293 if (!pw)
1294 return NULL;
1295 if (n == 0 && !isl_space_is_named_or_nested(pw->dim, type))
1296 return pw;
1298 set_type = type == isl_dim_in ? isl_dim_set : type;
1300 pw = FN(PW,cow)(pw);
1301 if (!pw)
1302 return NULL;
1304 pw->dim = isl_space_insert_dims(pw->dim, type, first, n);
1305 if (!pw->dim)
1306 goto error;
1308 for (i = 0; i < pw->n; ++i) {
1309 pw->p[i].set = isl_set_insert_dims(pw->p[i].set,
1310 set_type, first, n);
1311 if (!pw->p[i].set)
1312 goto error;
1313 pw->p[i].FIELD = FN(EL,insert_dims)(pw->p[i].FIELD,
1314 type, first, n);
1315 if (!pw->p[i].FIELD)
1316 goto error;
1319 return pw;
1320 error:
1321 FN(PW,free)(pw);
1322 return NULL;
1324 #endif
1326 __isl_give PW *FN(PW,fix_dim)(__isl_take PW *pw,
1327 enum isl_dim_type type, unsigned pos, isl_int v)
1329 int i;
1331 if (!pw)
1332 return NULL;
1334 if (type == isl_dim_in)
1335 type = isl_dim_set;
1337 pw = FN(PW,cow)(pw);
1338 if (!pw)
1339 return NULL;
1340 for (i = 0; i < pw->n; ++i) {
1341 pw->p[i].set = isl_set_fix(pw->p[i].set, type, pos, v);
1342 if (FN(PW,exploit_equalities_and_remove_if_empty)(pw, i) < 0)
1343 return FN(PW,free)(pw);
1346 return pw;
1349 /* Fix the value of the variable at position "pos" of type "type" of "pw"
1350 * to be equal to "v".
1352 __isl_give PW *FN(PW,fix_val)(__isl_take PW *pw,
1353 enum isl_dim_type type, unsigned pos, __isl_take isl_val *v)
1355 if (!v)
1356 return FN(PW,free)(pw);
1357 if (!isl_val_is_int(v))
1358 isl_die(FN(PW,get_ctx)(pw), isl_error_invalid,
1359 "expecting integer value", goto error);
1361 pw = FN(PW,fix_dim)(pw, type, pos, v->n);
1362 isl_val_free(v);
1364 return pw;
1365 error:
1366 isl_val_free(v);
1367 return FN(PW,free)(pw);
1370 unsigned FN(PW,dim)(__isl_keep PW *pw, enum isl_dim_type type)
1372 return pw ? isl_space_dim(pw->dim, type) : 0;
1375 __isl_give PW *FN(PW,split_dims)(__isl_take PW *pw,
1376 enum isl_dim_type type, unsigned first, unsigned n)
1378 int i;
1380 if (!pw)
1381 return NULL;
1382 if (n == 0)
1383 return pw;
1385 if (type == isl_dim_in)
1386 type = isl_dim_set;
1388 pw = FN(PW,cow)(pw);
1389 if (!pw)
1390 return NULL;
1391 if (!pw->dim)
1392 goto error;
1393 for (i = 0; i < pw->n; ++i) {
1394 pw->p[i].set = isl_set_split_dims(pw->p[i].set, type, first, n);
1395 if (!pw->p[i].set)
1396 goto error;
1399 return pw;
1400 error:
1401 FN(PW,free)(pw);
1402 return NULL;
1405 #ifndef NO_OPT
1406 /* Compute the maximal value attained by the piecewise quasipolynomial
1407 * on its domain or zero if the domain is empty.
1408 * In the worst case, the domain is scanned completely,
1409 * so the domain is assumed to be bounded.
1411 __isl_give isl_val *FN(PW,opt)(__isl_take PW *pw, int max)
1413 int i;
1414 isl_val *opt;
1416 if (!pw)
1417 return NULL;
1419 if (pw->n == 0) {
1420 opt = isl_val_zero(FN(PW,get_ctx)(pw));
1421 FN(PW,free)(pw);
1422 return opt;
1425 opt = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[0].FIELD),
1426 isl_set_copy(pw->p[0].set), max);
1427 for (i = 1; i < pw->n; ++i) {
1428 isl_val *opt_i;
1429 opt_i = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[i].FIELD),
1430 isl_set_copy(pw->p[i].set), max);
1431 if (max)
1432 opt = isl_val_max(opt, opt_i);
1433 else
1434 opt = isl_val_min(opt, opt_i);
1437 FN(PW,free)(pw);
1438 return opt;
1441 __isl_give isl_val *FN(PW,max)(__isl_take PW *pw)
1443 return FN(PW,opt)(pw, 1);
1446 __isl_give isl_val *FN(PW,min)(__isl_take PW *pw)
1448 return FN(PW,opt)(pw, 0);
1450 #endif
1452 __isl_give isl_space *FN(PW,get_space)(__isl_keep PW *pw)
1454 return pw ? isl_space_copy(pw->dim) : NULL;
1457 __isl_give isl_space *FN(PW,get_domain_space)(__isl_keep PW *pw)
1459 return pw ? isl_space_domain(isl_space_copy(pw->dim)) : NULL;
1462 /* Return the position of the dimension of the given type and name
1463 * in "pw".
1464 * Return -1 if no such dimension can be found.
1466 int FN(PW,find_dim_by_name)(__isl_keep PW *pw,
1467 enum isl_dim_type type, const char *name)
1469 if (!pw)
1470 return -1;
1471 return isl_space_find_dim_by_name(pw->dim, type, name);
1474 #ifndef NO_RESET_DIM
1475 /* Reset the space of "pw". Since we don't know if the elements
1476 * represent the spaces themselves or their domains, we pass along
1477 * both when we call their reset_space_and_domain.
1479 static __isl_give PW *FN(PW,reset_space_and_domain)(__isl_take PW *pw,
1480 __isl_take isl_space *space, __isl_take isl_space *domain)
1482 int i;
1484 pw = FN(PW,cow)(pw);
1485 if (!pw || !space || !domain)
1486 goto error;
1488 for (i = 0; i < pw->n; ++i) {
1489 pw->p[i].set = isl_set_reset_space(pw->p[i].set,
1490 isl_space_copy(domain));
1491 if (!pw->p[i].set)
1492 goto error;
1493 pw->p[i].FIELD = FN(EL,reset_space_and_domain)(pw->p[i].FIELD,
1494 isl_space_copy(space), isl_space_copy(domain));
1495 if (!pw->p[i].FIELD)
1496 goto error;
1499 isl_space_free(domain);
1501 isl_space_free(pw->dim);
1502 pw->dim = space;
1504 return pw;
1505 error:
1506 isl_space_free(domain);
1507 isl_space_free(space);
1508 FN(PW,free)(pw);
1509 return NULL;
1512 __isl_give PW *FN(PW,reset_domain_space)(__isl_take PW *pw,
1513 __isl_take isl_space *domain)
1515 isl_space *space;
1517 space = isl_space_extend_domain_with_range(isl_space_copy(domain),
1518 FN(PW,get_space)(pw));
1519 return FN(PW,reset_space_and_domain)(pw, space, domain);
1522 __isl_give PW *FN(PW,reset_space)(__isl_take PW *pw, __isl_take isl_space *dim)
1524 isl_space *domain;
1526 domain = isl_space_domain(isl_space_copy(dim));
1527 return FN(PW,reset_space_and_domain)(pw, dim, domain);
1530 __isl_give PW *FN(PW,set_tuple_id)(__isl_take PW *pw, enum isl_dim_type type,
1531 __isl_take isl_id *id)
1533 isl_space *space;
1535 pw = FN(PW,cow)(pw);
1536 if (!pw)
1537 goto error;
1539 space = FN(PW,get_space)(pw);
1540 space = isl_space_set_tuple_id(space, type, id);
1542 return FN(PW,reset_space)(pw, space);
1543 error:
1544 isl_id_free(id);
1545 return FN(PW,free)(pw);
1548 /* Drop the id on the specified tuple.
1550 __isl_give PW *FN(PW,reset_tuple_id)(__isl_take PW *pw, enum isl_dim_type type)
1552 isl_space *space;
1554 if (!pw)
1555 return NULL;
1556 if (!FN(PW,has_tuple_id)(pw, type))
1557 return pw;
1559 pw = FN(PW,cow)(pw);
1560 if (!pw)
1561 return NULL;
1563 space = FN(PW,get_space)(pw);
1564 space = isl_space_reset_tuple_id(space, type);
1566 return FN(PW,reset_space)(pw, space);
1569 __isl_give PW *FN(PW,set_dim_id)(__isl_take PW *pw,
1570 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
1572 pw = FN(PW,cow)(pw);
1573 if (!pw)
1574 goto error;
1575 pw->dim = isl_space_set_dim_id(pw->dim, type, pos, id);
1576 return FN(PW,reset_space)(pw, isl_space_copy(pw->dim));
1577 error:
1578 isl_id_free(id);
1579 return FN(PW,free)(pw);
1581 #endif
1583 /* Reset the user pointer on all identifiers of parameters and tuples
1584 * of the space of "pw".
1586 __isl_give PW *FN(PW,reset_user)(__isl_take PW *pw)
1588 isl_space *space;
1590 space = FN(PW,get_space)(pw);
1591 space = isl_space_reset_user(space);
1593 return FN(PW,reset_space)(pw, space);
1596 int FN(PW,has_equal_space)(__isl_keep PW *pw1, __isl_keep PW *pw2)
1598 if (!pw1 || !pw2)
1599 return -1;
1601 return isl_space_is_equal(pw1->dim, pw2->dim);
1604 #ifndef NO_MORPH
1605 __isl_give PW *FN(PW,morph_domain)(__isl_take PW *pw,
1606 __isl_take isl_morph *morph)
1608 int i;
1609 isl_ctx *ctx;
1611 if (!pw || !morph)
1612 goto error;
1614 ctx = isl_space_get_ctx(pw->dim);
1615 isl_assert(ctx, isl_space_is_domain_internal(morph->dom->dim, pw->dim),
1616 goto error);
1618 pw = FN(PW,cow)(pw);
1619 if (!pw)
1620 goto error;
1621 pw->dim = isl_space_extend_domain_with_range(
1622 isl_space_copy(morph->ran->dim), pw->dim);
1623 if (!pw->dim)
1624 goto error;
1626 for (i = 0; i < pw->n; ++i) {
1627 pw->p[i].set = isl_morph_set(isl_morph_copy(morph), pw->p[i].set);
1628 if (!pw->p[i].set)
1629 goto error;
1630 pw->p[i].FIELD = FN(EL,morph_domain)(pw->p[i].FIELD,
1631 isl_morph_copy(morph));
1632 if (!pw->p[i].FIELD)
1633 goto error;
1636 isl_morph_free(morph);
1638 return pw;
1639 error:
1640 FN(PW,free)(pw);
1641 isl_morph_free(morph);
1642 return NULL;
1644 #endif
1646 int FN(PW,n_piece)(__isl_keep PW *pw)
1648 return pw ? pw->n : 0;
1651 isl_stat FN(PW,foreach_piece)(__isl_keep PW *pw,
1652 isl_stat (*fn)(__isl_take isl_set *set, __isl_take EL *el, void *user),
1653 void *user)
1655 int i;
1657 if (!pw)
1658 return isl_stat_error;
1660 for (i = 0; i < pw->n; ++i)
1661 if (fn(isl_set_copy(pw->p[i].set),
1662 FN(EL,copy)(pw->p[i].FIELD), user) < 0)
1663 return isl_stat_error;
1665 return isl_stat_ok;
1668 #ifndef NO_LIFT
1669 static int any_divs(__isl_keep isl_set *set)
1671 int i;
1673 if (!set)
1674 return -1;
1676 for (i = 0; i < set->n; ++i)
1677 if (set->p[i]->n_div > 0)
1678 return 1;
1680 return 0;
1683 static isl_stat foreach_lifted_subset(__isl_take isl_set *set,
1684 __isl_take EL *el,
1685 isl_stat (*fn)(__isl_take isl_set *set, __isl_take EL *el,
1686 void *user), void *user)
1688 int i;
1690 if (!set || !el)
1691 goto error;
1693 for (i = 0; i < set->n; ++i) {
1694 isl_set *lift;
1695 EL *copy;
1697 lift = isl_set_from_basic_set(isl_basic_set_copy(set->p[i]));
1698 lift = isl_set_lift(lift);
1700 copy = FN(EL,copy)(el);
1701 copy = FN(EL,lift)(copy, isl_set_get_space(lift));
1703 if (fn(lift, copy, user) < 0)
1704 goto error;
1707 isl_set_free(set);
1708 FN(EL,free)(el);
1710 return isl_stat_ok;
1711 error:
1712 isl_set_free(set);
1713 FN(EL,free)(el);
1714 return isl_stat_error;
1717 isl_stat FN(PW,foreach_lifted_piece)(__isl_keep PW *pw,
1718 isl_stat (*fn)(__isl_take isl_set *set, __isl_take EL *el,
1719 void *user), void *user)
1721 int i;
1723 if (!pw)
1724 return isl_stat_error;
1726 for (i = 0; i < pw->n; ++i) {
1727 isl_set *set;
1728 EL *el;
1730 set = isl_set_copy(pw->p[i].set);
1731 el = FN(EL,copy)(pw->p[i].FIELD);
1732 if (!any_divs(set)) {
1733 if (fn(set, el, user) < 0)
1734 return isl_stat_error;
1735 continue;
1737 if (foreach_lifted_subset(set, el, fn, user) < 0)
1738 return isl_stat_error;
1741 return isl_stat_ok;
1743 #endif
1745 #ifndef NO_MOVE_DIMS
1746 __isl_give PW *FN(PW,move_dims)(__isl_take PW *pw,
1747 enum isl_dim_type dst_type, unsigned dst_pos,
1748 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1750 int i;
1752 pw = FN(PW,cow)(pw);
1753 if (!pw)
1754 return NULL;
1756 pw->dim = isl_space_move_dims(pw->dim, dst_type, dst_pos, src_type, src_pos, n);
1757 if (!pw->dim)
1758 goto error;
1760 for (i = 0; i < pw->n; ++i) {
1761 pw->p[i].FIELD = FN(EL,move_dims)(pw->p[i].FIELD,
1762 dst_type, dst_pos, src_type, src_pos, n);
1763 if (!pw->p[i].FIELD)
1764 goto error;
1767 if (dst_type == isl_dim_in)
1768 dst_type = isl_dim_set;
1769 if (src_type == isl_dim_in)
1770 src_type = isl_dim_set;
1772 for (i = 0; i < pw->n; ++i) {
1773 pw->p[i].set = isl_set_move_dims(pw->p[i].set,
1774 dst_type, dst_pos,
1775 src_type, src_pos, n);
1776 if (!pw->p[i].set)
1777 goto error;
1780 return pw;
1781 error:
1782 FN(PW,free)(pw);
1783 return NULL;
1785 #endif
1787 __isl_give PW *FN(PW,mul_isl_int)(__isl_take PW *pw, isl_int v)
1789 int i;
1791 if (isl_int_is_one(v))
1792 return pw;
1793 if (pw && DEFAULT_IS_ZERO && isl_int_is_zero(v)) {
1794 PW *zero;
1795 isl_space *dim = FN(PW,get_space)(pw);
1796 #ifdef HAS_TYPE
1797 zero = FN(PW,ZERO)(dim, pw->type);
1798 #else
1799 zero = FN(PW,ZERO)(dim);
1800 #endif
1801 FN(PW,free)(pw);
1802 return zero;
1804 pw = FN(PW,cow)(pw);
1805 if (!pw)
1806 return NULL;
1807 if (pw->n == 0)
1808 return pw;
1810 #ifdef HAS_TYPE
1811 if (isl_int_is_neg(v))
1812 pw->type = isl_fold_type_negate(pw->type);
1813 #endif
1814 for (i = 0; i < pw->n; ++i) {
1815 pw->p[i].FIELD = FN(EL,scale)(pw->p[i].FIELD, v);
1816 if (!pw->p[i].FIELD)
1817 goto error;
1820 return pw;
1821 error:
1822 FN(PW,free)(pw);
1823 return NULL;
1826 /* Multiply the pieces of "pw" by "v" and return the result.
1828 __isl_give PW *FN(PW,scale_val)(__isl_take PW *pw, __isl_take isl_val *v)
1830 int i;
1832 if (!pw || !v)
1833 goto error;
1835 if (isl_val_is_one(v)) {
1836 isl_val_free(v);
1837 return pw;
1839 if (pw && DEFAULT_IS_ZERO && isl_val_is_zero(v)) {
1840 PW *zero;
1841 isl_space *space = FN(PW,get_space)(pw);
1842 #ifdef HAS_TYPE
1843 zero = FN(PW,ZERO)(space, pw->type);
1844 #else
1845 zero = FN(PW,ZERO)(space);
1846 #endif
1847 FN(PW,free)(pw);
1848 isl_val_free(v);
1849 return zero;
1851 if (pw->n == 0) {
1852 isl_val_free(v);
1853 return pw;
1855 pw = FN(PW,cow)(pw);
1856 if (!pw)
1857 goto error;
1859 #ifdef HAS_TYPE
1860 if (isl_val_is_neg(v))
1861 pw->type = isl_fold_type_negate(pw->type);
1862 #endif
1863 for (i = 0; i < pw->n; ++i) {
1864 pw->p[i].FIELD = FN(EL,scale_val)(pw->p[i].FIELD,
1865 isl_val_copy(v));
1866 if (!pw->p[i].FIELD)
1867 goto error;
1870 isl_val_free(v);
1871 return pw;
1872 error:
1873 isl_val_free(v);
1874 FN(PW,free)(pw);
1875 return NULL;
1878 /* Divide the pieces of "pw" by "v" and return the result.
1880 __isl_give PW *FN(PW,scale_down_val)(__isl_take PW *pw, __isl_take isl_val *v)
1882 int i;
1884 if (!pw || !v)
1885 goto error;
1887 if (isl_val_is_one(v)) {
1888 isl_val_free(v);
1889 return pw;
1892 if (!isl_val_is_rat(v))
1893 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1894 "expecting rational factor", goto error);
1895 if (isl_val_is_zero(v))
1896 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1897 "cannot scale down by zero", goto error);
1899 if (pw->n == 0) {
1900 isl_val_free(v);
1901 return pw;
1903 pw = FN(PW,cow)(pw);
1904 if (!pw)
1905 goto error;
1907 #ifdef HAS_TYPE
1908 if (isl_val_is_neg(v))
1909 pw->type = isl_fold_type_negate(pw->type);
1910 #endif
1911 for (i = 0; i < pw->n; ++i) {
1912 pw->p[i].FIELD = FN(EL,scale_down_val)(pw->p[i].FIELD,
1913 isl_val_copy(v));
1914 if (!pw->p[i].FIELD)
1915 goto error;
1918 isl_val_free(v);
1919 return pw;
1920 error:
1921 isl_val_free(v);
1922 FN(PW,free)(pw);
1923 return NULL;
1926 __isl_give PW *FN(PW,scale)(__isl_take PW *pw, isl_int v)
1928 return FN(PW,mul_isl_int)(pw, v);
1931 /* Apply some normalization to "pw".
1932 * In particular, sort the pieces according to their function value
1933 * expressions, combining pairs of adjacent pieces with
1934 * the same such expression, and then normalize the domains of the pieces.
1936 * We normalize in place, but if anything goes wrong we need
1937 * to return NULL, so we need to make sure we don't change the
1938 * meaning of any possible other copies of "pw".
1940 __isl_give PW *FN(PW,normalize)(__isl_take PW *pw)
1942 int i;
1943 isl_set *set;
1945 pw = FN(PW,sort)(pw);
1946 if (!pw)
1947 return NULL;
1948 for (i = 0; i < pw->n; ++i) {
1949 set = isl_set_normalize(isl_set_copy(pw->p[i].set));
1950 if (!set)
1951 return FN(PW,free)(pw);
1952 isl_set_free(pw->p[i].set);
1953 pw->p[i].set = set;
1956 return pw;
1959 /* Is pw1 obviously equal to pw2?
1960 * That is, do they have obviously identical cells and obviously identical
1961 * elements on each cell?
1963 isl_bool FN(PW,plain_is_equal)(__isl_keep PW *pw1, __isl_keep PW *pw2)
1965 int i;
1966 isl_bool equal;
1968 if (!pw1 || !pw2)
1969 return isl_bool_error;
1971 if (pw1 == pw2)
1972 return isl_bool_true;
1973 if (!isl_space_is_equal(pw1->dim, pw2->dim))
1974 return isl_bool_false;
1976 pw1 = FN(PW,copy)(pw1);
1977 pw2 = FN(PW,copy)(pw2);
1978 pw1 = FN(PW,normalize)(pw1);
1979 pw2 = FN(PW,normalize)(pw2);
1980 if (!pw1 || !pw2)
1981 goto error;
1983 equal = pw1->n == pw2->n;
1984 for (i = 0; equal && i < pw1->n; ++i) {
1985 equal = isl_set_plain_is_equal(pw1->p[i].set, pw2->p[i].set);
1986 if (equal < 0)
1987 goto error;
1988 if (!equal)
1989 break;
1990 equal = FN(EL,plain_is_equal)(pw1->p[i].FIELD, pw2->p[i].FIELD);
1991 if (equal < 0)
1992 goto error;
1995 FN(PW,free)(pw1);
1996 FN(PW,free)(pw2);
1997 return equal;
1998 error:
1999 FN(PW,free)(pw1);
2000 FN(PW,free)(pw2);
2001 return isl_bool_error;
2004 #ifndef NO_PULLBACK
2005 static __isl_give PW *FN(PW,align_params_pw_multi_aff_and)(__isl_take PW *pw,
2006 __isl_take isl_multi_aff *ma,
2007 __isl_give PW *(*fn)(__isl_take PW *pw, __isl_take isl_multi_aff *ma))
2009 isl_ctx *ctx;
2010 isl_space *ma_space;
2012 ma_space = isl_multi_aff_get_space(ma);
2013 if (!pw || !ma || !ma_space)
2014 goto error;
2015 if (isl_space_match(pw->dim, isl_dim_param, ma_space, isl_dim_param)) {
2016 isl_space_free(ma_space);
2017 return fn(pw, ma);
2019 ctx = FN(PW,get_ctx)(pw);
2020 if (!isl_space_has_named_params(pw->dim) ||
2021 !isl_space_has_named_params(ma_space))
2022 isl_die(ctx, isl_error_invalid,
2023 "unaligned unnamed parameters", goto error);
2024 pw = FN(PW,align_params)(pw, ma_space);
2025 ma = isl_multi_aff_align_params(ma, FN(PW,get_space)(pw));
2026 return fn(pw, ma);
2027 error:
2028 isl_space_free(ma_space);
2029 FN(PW,free)(pw);
2030 isl_multi_aff_free(ma);
2031 return NULL;
2034 static __isl_give PW *FN(PW,align_params_pw_pw_multi_aff_and)(__isl_take PW *pw,
2035 __isl_take isl_pw_multi_aff *pma,
2036 __isl_give PW *(*fn)(__isl_take PW *pw,
2037 __isl_take isl_pw_multi_aff *ma))
2039 isl_ctx *ctx;
2040 isl_space *pma_space;
2042 pma_space = isl_pw_multi_aff_get_space(pma);
2043 if (!pw || !pma || !pma_space)
2044 goto error;
2045 if (isl_space_match(pw->dim, isl_dim_param, pma_space, isl_dim_param)) {
2046 isl_space_free(pma_space);
2047 return fn(pw, pma);
2049 ctx = FN(PW,get_ctx)(pw);
2050 if (!isl_space_has_named_params(pw->dim) ||
2051 !isl_space_has_named_params(pma_space))
2052 isl_die(ctx, isl_error_invalid,
2053 "unaligned unnamed parameters", goto error);
2054 pw = FN(PW,align_params)(pw, pma_space);
2055 pma = isl_pw_multi_aff_align_params(pma, FN(PW,get_space)(pw));
2056 return fn(pw, pma);
2057 error:
2058 isl_space_free(pma_space);
2059 FN(PW,free)(pw);
2060 isl_pw_multi_aff_free(pma);
2061 return NULL;
2064 /* Compute the pullback of "pw" by the function represented by "ma".
2065 * In other words, plug in "ma" in "pw".
2067 static __isl_give PW *FN(PW,pullback_multi_aff_aligned)(__isl_take PW *pw,
2068 __isl_take isl_multi_aff *ma)
2070 int i;
2071 isl_space *space = NULL;
2073 ma = isl_multi_aff_align_divs(ma);
2074 pw = FN(PW,cow)(pw);
2075 if (!pw || !ma)
2076 goto error;
2078 space = isl_space_join(isl_multi_aff_get_space(ma),
2079 FN(PW,get_space)(pw));
2081 for (i = 0; i < pw->n; ++i) {
2082 pw->p[i].set = isl_set_preimage_multi_aff(pw->p[i].set,
2083 isl_multi_aff_copy(ma));
2084 if (!pw->p[i].set)
2085 goto error;
2086 pw->p[i].FIELD = FN(EL,pullback_multi_aff)(pw->p[i].FIELD,
2087 isl_multi_aff_copy(ma));
2088 if (!pw->p[i].FIELD)
2089 goto error;
2092 pw = FN(PW,reset_space)(pw, space);
2093 isl_multi_aff_free(ma);
2094 return pw;
2095 error:
2096 isl_space_free(space);
2097 isl_multi_aff_free(ma);
2098 FN(PW,free)(pw);
2099 return NULL;
2102 __isl_give PW *FN(PW,pullback_multi_aff)(__isl_take PW *pw,
2103 __isl_take isl_multi_aff *ma)
2105 return FN(PW,align_params_pw_multi_aff_and)(pw, ma,
2106 &FN(PW,pullback_multi_aff_aligned));
2109 /* Compute the pullback of "pw" by the function represented by "pma".
2110 * In other words, plug in "pma" in "pw".
2112 static __isl_give PW *FN(PW,pullback_pw_multi_aff_aligned)(__isl_take PW *pw,
2113 __isl_take isl_pw_multi_aff *pma)
2115 int i;
2116 PW *res;
2118 if (!pma)
2119 goto error;
2121 if (pma->n == 0) {
2122 isl_space *space;
2123 space = isl_space_join(isl_pw_multi_aff_get_space(pma),
2124 FN(PW,get_space)(pw));
2125 isl_pw_multi_aff_free(pma);
2126 res = FN(PW,empty)(space);
2127 FN(PW,free)(pw);
2128 return res;
2131 res = FN(PW,pullback_multi_aff)(FN(PW,copy)(pw),
2132 isl_multi_aff_copy(pma->p[0].maff));
2133 res = FN(PW,intersect_domain)(res, isl_set_copy(pma->p[0].set));
2135 for (i = 1; i < pma->n; ++i) {
2136 PW *res_i;
2138 res_i = FN(PW,pullback_multi_aff)(FN(PW,copy)(pw),
2139 isl_multi_aff_copy(pma->p[i].maff));
2140 res_i = FN(PW,intersect_domain)(res_i,
2141 isl_set_copy(pma->p[i].set));
2142 res = FN(PW,add_disjoint)(res, res_i);
2145 isl_pw_multi_aff_free(pma);
2146 FN(PW,free)(pw);
2147 return res;
2148 error:
2149 isl_pw_multi_aff_free(pma);
2150 FN(PW,free)(pw);
2151 return NULL;
2154 __isl_give PW *FN(PW,pullback_pw_multi_aff)(__isl_take PW *pw,
2155 __isl_take isl_pw_multi_aff *pma)
2157 return FN(PW,align_params_pw_pw_multi_aff_and)(pw, pma,
2158 &FN(PW,pullback_pw_multi_aff_aligned));
2160 #endif