?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
add test for coalescing of rational sets
[isl.git] / isl_pw_templ.c
blob59a69d9c2e6cdbcabc1b88e648705a33cb16400c
1 /*
2 * Copyright 2010-2011 INRIA Saclay
3 * Copyright 2011 Sven Verdoolaege
4 * Copyright 2012-2014 Ecole Normale Superieure
5 *
6 * Use of this software is governed by the MIT license
7 *
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
12 */
13
14 #include <isl/id.h>
15 #include <isl/aff.h>
16 #include <isl_sort.h>
17 #include <isl_val_private.h>
18
19 #include <isl_pw_macro.h>
20
21 #include "opt_type.h"
22
23 __isl_give PW *FN(PW,alloc_size)(__isl_take isl_space *space
24 OPT_TYPE_PARAM, int n)
25 {
26 isl_ctx *ctx;
27 struct PW *pw;
28
29 if (!space)
30 return NULL;
31 ctx = isl_space_get_ctx(space);
32 isl_assert(ctx, n >= 0, goto error);
33 pw = isl_alloc(ctx, struct PW,
34 sizeof(struct PW) + (n - 1) * sizeof(S(PW,piece)));
35 if (!pw)
36 goto error;
37
38 pw->ref = 1;
39 OPT_SET_TYPE(pw->, type);
40 pw->size = n;
41 pw->n = 0;
42 pw->dim = space;
43 return pw;
44 error:
45 isl_space_free(space);
46 return NULL;
47 }
48
49 __isl_give PW *FN(PW,ZERO)(__isl_take isl_space *space OPT_TYPE_PARAM)
50 {
51 return FN(PW,alloc_size)(space OPT_TYPE_ARG(NO_LOC), 0);
52 }
53
54 /* Add a piece with domain "set" and base expression "el"
55 * to the piecewise expression "pw".
56 *
57 * Do this independently of the values of "set" and "el",
58 * such that this function can be used by isl_pw_*_dup.
59 */
60 __isl_give PW *FN(PW,add_dup_piece)(__isl_take PW *pw,
61 __isl_take isl_set *set, __isl_take EL *el)
62 {
63 isl_ctx *ctx;
64 isl_space *el_dim = NULL;
65
66 if (!pw || !set || !el)
67 goto error;
68
69 ctx = isl_set_get_ctx(set);
70 if (!OPT_EQUAL_TYPES(pw->, el->))
71 isl_die(ctx, isl_error_invalid, "fold types don't match",
72 goto error);
73 el_dim = FN(EL,get_space(el));
74 isl_assert(ctx, isl_space_is_equal(pw->dim, el_dim), goto error);
75 isl_assert(ctx, pw->n < pw->size, goto error);
76
77 pw->p[pw->n].set = set;
78 pw->p[pw->n].FIELD = el;
79 pw->n++;
80
81 isl_space_free(el_dim);
82 return pw;
83 error:
84 isl_space_free(el_dim);
85 FN(PW,free)(pw);
86 isl_set_free(set);
87 FN(EL,free)(el);
88 return NULL;
89 }
90
91 /* Add a piece with domain "set" and base expression "el"
92 * to the piecewise expression "pw", provided the domain
93 * is not obviously empty and the base expression
94 * is not equal to the default value.
95 */
96 __isl_give PW *FN(PW,add_piece)(__isl_take PW *pw,
97 __isl_take isl_set *set, __isl_take EL *el)
98 {
99 isl_bool skip;
100
101 skip = isl_set_plain_is_empty(set);
102 if (skip >= 0 && !skip)
103 skip = FN(EL,EL_IS_ZERO)(el);
104 if (skip >= 0 && !skip)
105 return FN(PW,add_dup_piece)(pw, set, el);
106
107 isl_set_free(set);
108 FN(EL,free)(el);
109 if (skip < 0)
110 return FN(PW,free)(pw);
111 return pw;
112 }
113
114 /* Does the space of "set" correspond to that of the domain of "el".
115 */
116 static isl_bool FN(PW,compatible_domain)(__isl_keep EL *el,
117 __isl_keep isl_set *set)
118 {
119 isl_bool ok;
120 isl_space *el_space, *set_space;
121
122 if (!set || !el)
123 return isl_bool_error;
124 set_space = isl_set_get_space(set);
125 el_space = FN(EL,get_space)(el);
126 ok = isl_space_is_domain_internal(set_space, el_space);
127 isl_space_free(el_space);
128 isl_space_free(set_space);
129 return ok;
130 }
131
132 /* Check that the space of "set" corresponds to that of the domain of "el".
133 */
134 static isl_stat FN(PW,check_compatible_domain)(__isl_keep EL *el,
135 __isl_keep isl_set *set)
136 {
137 isl_bool ok;
138
139 ok = FN(PW,compatible_domain)(el, set);
140 if (ok < 0)
141 return isl_stat_error;
142 if (!ok)
143 isl_die(isl_set_get_ctx(set), isl_error_invalid,
144 "incompatible spaces", return isl_stat_error);
145
146 return isl_stat_ok;
147 }
148
149 __isl_give PW *FN(PW,alloc)(OPT_TYPE_PARAM_FIRST
150 __isl_take isl_set *set, __isl_take EL *el)
151 {
152 PW *pw;
153
154 if (FN(PW,check_compatible_domain)(el, set) < 0)
155 goto error;
156
157 pw = FN(PW,alloc_size)(FN(EL,get_space)(el) OPT_TYPE_ARG(NO_LOC), 1);
158
159 return FN(PW,add_piece)(pw, set, el);
160 error:
161 isl_set_free(set);
162 FN(EL,free)(el);
163 return NULL;
164 }
165
166 __isl_give PW *FN(PW,dup)(__isl_keep PW *pw)
167 {
168 int i;
169 PW *dup;
170
171 if (!pw)
172 return NULL;
173
174 dup = FN(PW,alloc_size)(isl_space_copy(pw->dim)
175 OPT_TYPE_ARG(pw->), pw->n);
176 if (!dup)
177 return NULL;
178
179 for (i = 0; i < pw->n; ++i)
180 dup = FN(PW,add_dup_piece)(dup, isl_set_copy(pw->p[i].set),
181 FN(EL,copy)(pw->p[i].FIELD));
182
183 return dup;
184 }
185
186 __isl_give PW *FN(PW,cow)(__isl_take PW *pw)
187 {
188 if (!pw)
189 return NULL;
190
191 if (pw->ref == 1)
192 return pw;
193 pw->ref--;
194 return FN(PW,dup)(pw);
195 }
196
197 __isl_give PW *FN(PW,copy)(__isl_keep PW *pw)
198 {
199 if (!pw)
200 return NULL;
201
202 pw->ref++;
203 return pw;
204 }
205
206 __isl_null PW *FN(PW,free)(__isl_take PW *pw)
207 {
208 int i;
209
210 if (!pw)
211 return NULL;
212 if (--pw->ref > 0)
213 return NULL;
214
215 for (i = 0; i < pw->n; ++i) {
216 isl_set_free(pw->p[i].set);
217 FN(EL,free)(pw->p[i].FIELD);
218 }
219 isl_space_free(pw->dim);
220 free(pw);
221
222 return NULL;
223 }
224
225 /* Create a piecewise expression with the given base expression on a universe
226 * domain.
227 */
228 static __isl_give PW *FN(FN(FN(PW,from),BASE),type_base)(__isl_take EL *el
229 OPT_TYPE_PARAM)
230 {
231 isl_set *dom = isl_set_universe(FN(EL,get_domain_space)(el));
232 return FN(PW,alloc)(OPT_TYPE_ARG_FIRST(NO_LOC) dom, el);
233 }
234
235 /* Create a piecewise expression with the given base expression on a universe
236 * domain.
237 *
238 * If the default value of this piecewise type is zero and
239 * if "el" is effectively zero, then create an empty piecewise expression
240 * instead.
241 */
242 static __isl_give PW *FN(FN(FN(PW,from),BASE),type)(__isl_take EL *el
243 OPT_TYPE_PARAM)
244 {
245 isl_bool is_zero;
246 isl_space *space;
247
248 if (!DEFAULT_IS_ZERO)
249 return FN(FN(FN(PW,from),BASE),type_base)(el
250 OPT_TYPE_ARG(NO_LOC));
251 is_zero = FN(EL,EL_IS_ZERO)(el);
252 if (is_zero < 0)
253 goto error;
254 if (!is_zero)
255 return FN(FN(FN(PW,from),BASE),type_base)(el
256 OPT_TYPE_ARG(NO_LOC));
257 space = FN(EL,get_space)(el);
258 FN(EL,free)(el);
259 return FN(PW,ZERO)(space OPT_TYPE_ARG(NO_LOC));
260 error:
261 FN(EL,free)(el);
262 return NULL;
263 }
264
265 #ifdef HAS_TYPE
266 /* Create a piecewise expression with the given base expression on a universe
267 * domain.
268 *
269 * Pass along the type as an extra argument for improved uniformity
270 * with piecewise types that do not have a fold type.
271 */
272 __isl_give PW *FN(FN(PW,from),BASE)(__isl_take EL *el)
273 {
274 enum isl_fold type = FN(EL,get_type)(el);
275 return FN(FN(FN(PW,from),BASE),type)(el, type);
276 }
277 #else
278 __isl_give PW *FN(FN(PW,from),BASE)(__isl_take EL *el)
279 {
280 return FN(FN(FN(PW,from),BASE),type)(el);
281 }
282 #endif
283
284 const char *FN(PW,get_dim_name)(__isl_keep PW *pw, enum isl_dim_type type,
285 unsigned pos)
286 {
287 return pw ? isl_space_get_dim_name(pw->dim, type, pos) : NULL;
288 }
289
290 isl_bool FN(PW,has_dim_id)(__isl_keep PW *pw, enum isl_dim_type type,
291 unsigned pos)
292 {
293 return pw ? isl_space_has_dim_id(pw->dim, type, pos) : isl_bool_error;
294 }
295
296 __isl_give isl_id *FN(PW,get_dim_id)(__isl_keep PW *pw, enum isl_dim_type type,
297 unsigned pos)
298 {
299 return pw ? isl_space_get_dim_id(pw->dim, type, pos) : NULL;
300 }
301
302 isl_bool FN(PW,has_tuple_name)(__isl_keep PW *pw, enum isl_dim_type type)
303 {
304 return pw ? isl_space_has_tuple_name(pw->dim, type) : isl_bool_error;
305 }
306
307 const char *FN(PW,get_tuple_name)(__isl_keep PW *pw, enum isl_dim_type type)
308 {
309 return pw ? isl_space_get_tuple_name(pw->dim, type) : NULL;
310 }
311
312 isl_bool FN(PW,has_tuple_id)(__isl_keep PW *pw, enum isl_dim_type type)
313 {
314 return pw ? isl_space_has_tuple_id(pw->dim, type) : isl_bool_error;
315 }
316
317 __isl_give isl_id *FN(PW,get_tuple_id)(__isl_keep PW *pw, enum isl_dim_type type)
318 {
319 return pw ? isl_space_get_tuple_id(pw->dim, type) : NULL;
320 }
321
322 isl_bool FN(PW,IS_ZERO)(__isl_keep PW *pw)
323 {
324 if (!pw)
325 return isl_bool_error;
326
327 return isl_bool_ok(pw->n == 0);
328 }
329
330 __isl_give PW *FN(PW,realign_domain)(__isl_take PW *pw,
331 __isl_take isl_reordering *exp)
332 {
333 int i;
334
335 pw = FN(PW,cow)(pw);
336 if (!pw || !exp)
337 goto error;
338
339 for (i = 0; i < pw->n; ++i) {
340 pw->p[i].set = isl_set_realign(pw->p[i].set,
341 isl_reordering_copy(exp));
342 if (!pw->p[i].set)
343 goto error;
344 pw->p[i].FIELD = FN(EL,realign_domain)(pw->p[i].FIELD,
345 isl_reordering_copy(exp));
346 if (!pw->p[i].FIELD)
347 goto error;
348 }
349
350 pw = FN(PW,reset_domain_space)(pw, isl_reordering_get_space(exp));
351
352 isl_reordering_free(exp);
353 return pw;
354 error:
355 isl_reordering_free(exp);
356 FN(PW,free)(pw);
357 return NULL;
358 }
359
360 #undef TYPE
361 #define TYPE PW
362
363 #include "isl_check_named_params_templ.c"
364
365 /* Align the parameters of "pw" to those of "model".
366 */
367 __isl_give PW *FN(PW,align_params)(__isl_take PW *pw, __isl_take isl_space *model)
368 {
369 isl_ctx *ctx;
370 isl_bool equal_params;
371
372 if (!pw || !model)
373 goto error;
374
375 ctx = isl_space_get_ctx(model);
376 if (!isl_space_has_named_params(model))
377 isl_die(ctx, isl_error_invalid,
378 "model has unnamed parameters", goto error);
379 if (FN(PW,check_named_params)(pw) < 0)
380 goto error;
381 equal_params = isl_space_has_equal_params(pw->dim, model);
382 if (equal_params < 0)
383 goto error;
384 if (!equal_params) {
385 isl_reordering *exp;
386
387 exp = isl_parameter_alignment_reordering(pw->dim, model);
388 exp = isl_reordering_extend_space(exp,
389 FN(PW,get_domain_space)(pw));
390 pw = FN(PW,realign_domain)(pw, exp);
391 }
392
393 isl_space_free(model);
394 return pw;
395 error:
396 isl_space_free(model);
397 FN(PW,free)(pw);
398 return NULL;
399 }
400
401 #undef TYPE
402 #define TYPE PW
403
404 static
405 #include "isl_align_params_bin_templ.c"
406
407 #undef SUFFIX
408 #define SUFFIX set
409 #undef ARG1
410 #define ARG1 PW
411 #undef ARG2
412 #define ARG2 isl_set
413
414 static
415 #include "isl_align_params_templ.c"
416
417 #undef TYPE
418 #define TYPE PW
419
420 #include "isl_type_has_equal_space_bin_templ.c"
421 #include "isl_type_check_equal_space_templ.c"
422
423 /* Private version of "union_add". For isl_pw_qpolynomial and
424 * isl_pw_qpolynomial_fold, we prefer to simply call it "add".
425 */
426 static __isl_give PW *FN(PW,union_add_)(__isl_take PW *pw1, __isl_take PW *pw2)
427 {
428 int i, j, n;
429 struct PW *res;
430 isl_ctx *ctx;
431 isl_set *set;
432
433 if (FN(PW,align_params_bin)(&pw1, &pw2) < 0)
434 goto error;
435
436 ctx = isl_space_get_ctx(pw1->dim);
437 if (!OPT_EQUAL_TYPES(pw1->, pw2->))
438 isl_die(ctx, isl_error_invalid,
439 "fold types don't match", goto error);
440 if (FN(PW,check_equal_space)(pw1, pw2) < 0)
441 goto error;
442
443 if (FN(PW,IS_ZERO)(pw1)) {
444 FN(PW,free)(pw1);
445 return pw2;
446 }
447
448 if (FN(PW,IS_ZERO)(pw2)) {
449 FN(PW,free)(pw2);
450 return pw1;
451 }
452
453 n = (pw1->n + 1) * (pw2->n + 1);
454 res = FN(PW,alloc_size)(isl_space_copy(pw1->dim)
455 OPT_TYPE_ARG(pw1->), n);
456
457 for (i = 0; i < pw1->n; ++i) {
458 set = isl_set_copy(pw1->p[i].set);
459 for (j = 0; j < pw2->n; ++j) {
460 struct isl_set *common;
461 EL *sum;
462 common = isl_set_intersect(isl_set_copy(pw1->p[i].set),
463 isl_set_copy(pw2->p[j].set));
464 if (isl_set_plain_is_empty(common)) {
465 isl_set_free(common);
466 continue;
467 }
468 set = isl_set_subtract(set,
469 isl_set_copy(pw2->p[j].set));
470
471 sum = FN(EL,add_on_domain)(common,
472 FN(EL,copy)(pw1->p[i].FIELD),
473 FN(EL,copy)(pw2->p[j].FIELD));
474
475 res = FN(PW,add_piece)(res, common, sum);
476 }
477 res = FN(PW,add_piece)(res, set, FN(EL,copy)(pw1->p[i].FIELD));
478 }
479
480 for (j = 0; j < pw2->n; ++j) {
481 set = isl_set_copy(pw2->p[j].set);
482 for (i = 0; i < pw1->n; ++i)
483 set = isl_set_subtract(set,
484 isl_set_copy(pw1->p[i].set));
485 res = FN(PW,add_piece)(res, set, FN(EL,copy)(pw2->p[j].FIELD));
486 }
487
488 FN(PW,free)(pw1);
489 FN(PW,free)(pw2);
490
491 return res;
492 error:
493 FN(PW,free)(pw1);
494 FN(PW,free)(pw2);
495 return NULL;
496 }
497
498 /* Make sure "pw" has room for at least "n" more pieces.
499 *
500 * If there is only one reference to pw, we extend it in place.
501 * Otherwise, we create a new PW and copy the pieces.
502 */
503 static __isl_give PW *FN(PW,grow)(__isl_take PW *pw, int n)
504 {
505 int i;
506 isl_ctx *ctx;
507 PW *res;
508
509 if (!pw)
510 return NULL;
511 if (pw->n + n <= pw->size)
512 return pw;
513 ctx = FN(PW,get_ctx)(pw);
514 n += pw->n;
515 if (pw->ref == 1) {
516 res = isl_realloc(ctx, pw, struct PW,
517 sizeof(struct PW) + (n - 1) * sizeof(S(PW,piece)));
518 if (!res)
519 return FN(PW,free)(pw);
520 res->size = n;
521 return res;
522 }
523 res = FN(PW,alloc_size)(isl_space_copy(pw->dim) OPT_TYPE_ARG(pw->), n);
524 if (!res)
525 return FN(PW,free)(pw);
526 for (i = 0; i < pw->n; ++i)
527 res = FN(PW,add_piece)(res, isl_set_copy(pw->p[i].set),
528 FN(EL,copy)(pw->p[i].FIELD));
529 FN(PW,free)(pw);
530 return res;
531 }
532
533 __isl_give PW *FN(PW,add_disjoint)(__isl_take PW *pw1, __isl_take PW *pw2)
534 {
535 int i;
536 isl_ctx *ctx;
537
538 if (FN(PW,align_params_bin)(&pw1, &pw2) < 0)
539 goto error;
540
541 if (pw1->size < pw1->n + pw2->n && pw1->n < pw2->n)
542 return FN(PW,add_disjoint)(pw2, pw1);
543
544 ctx = isl_space_get_ctx(pw1->dim);
545 if (!OPT_EQUAL_TYPES(pw1->, pw2->))
546 isl_die(ctx, isl_error_invalid,
547 "fold types don't match", goto error);
548 if (FN(PW,check_equal_space)(pw1, pw2) < 0)
549 goto error;
550
551 if (FN(PW,IS_ZERO)(pw1)) {
552 FN(PW,free)(pw1);
553 return pw2;
554 }
555
556 if (FN(PW,IS_ZERO)(pw2)) {
557 FN(PW,free)(pw2);
558 return pw1;
559 }
560
561 pw1 = FN(PW,grow)(pw1, pw2->n);
562 if (!pw1)
563 goto error;
564
565 for (i = 0; i < pw2->n; ++i)
566 pw1 = FN(PW,add_piece)(pw1,
567 isl_set_copy(pw2->p[i].set),
568 FN(EL,copy)(pw2->p[i].FIELD));
569
570 FN(PW,free)(pw2);
571
572 return pw1;
573 error:
574 FN(PW,free)(pw1);
575 FN(PW,free)(pw2);
576 return NULL;
577 }
578
579 /* This function is currently only used from isl_aff.c
580 */
581 static __isl_give PW *FN(PW,on_shared_domain_in)(__isl_take PW *pw1,
582 __isl_take PW *pw2, __isl_take isl_space *space,
583 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))
584 __attribute__ ((unused));
585
586 /* Apply "fn" to pairs of elements from pw1 and pw2 on shared domains.
587 * The result of "fn" (and therefore also of this function) lives in "space".
588 */
589 static __isl_give PW *FN(PW,on_shared_domain_in)(__isl_take PW *pw1,
590 __isl_take PW *pw2, __isl_take isl_space *space,
591 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))
592 {
593 int i, j, n;
594 PW *res = NULL;
595
596 if (!pw1 || !pw2)
597 goto error;
598
599 n = pw1->n * pw2->n;
600 res = FN(PW,alloc_size)(isl_space_copy(space) OPT_TYPE_ARG(pw1->), n);
601
602 for (i = 0; i < pw1->n; ++i) {
603 for (j = 0; j < pw2->n; ++j) {
604 isl_set *common;
605 EL *res_ij;
606 int empty;
607
608 common = isl_set_intersect(
609 isl_set_copy(pw1->p[i].set),
610 isl_set_copy(pw2->p[j].set));
611 empty = isl_set_plain_is_empty(common);
612 if (empty < 0 || empty) {
613 isl_set_free(common);
614 if (empty < 0)
615 goto error;
616 continue;
617 }
618
619 res_ij = fn(FN(EL,copy)(pw1->p[i].FIELD),
620 FN(EL,copy)(pw2->p[j].FIELD));
621 res_ij = FN(EL,gist)(res_ij, isl_set_copy(common));
622
623 res = FN(PW,add_piece)(res, common, res_ij);
624 }
625 }
626
627 isl_space_free(space);
628 FN(PW,free)(pw1);
629 FN(PW,free)(pw2);
630 return res;
631 error:
632 isl_space_free(space);
633 FN(PW,free)(pw1);
634 FN(PW,free)(pw2);
635 FN(PW,free)(res);
636 return NULL;
637 }
638
639 /* This function is currently only used from isl_aff.c
640 */
641 static __isl_give PW *FN(PW,on_shared_domain)(__isl_take PW *pw1,
642 __isl_take PW *pw2,
643 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))
644 __attribute__ ((unused));
645
646 /* Apply "fn" to pairs of elements from pw1 and pw2 on shared domains.
647 * The result of "fn" is assumed to live in the same space as "pw1" and "pw2".
648 */
649 static __isl_give PW *FN(PW,on_shared_domain)(__isl_take PW *pw1,
650 __isl_take PW *pw2,
651 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))
652 {
653 isl_space *space;
654
655 if (FN(PW,check_equal_space)(pw1, pw2) < 0)
656 goto error;
657
658 space = isl_space_copy(pw1->dim);
659 return FN(PW,on_shared_domain_in)(pw1, pw2, space, fn);
660 error:
661 FN(PW,free)(pw1);
662 FN(PW,free)(pw2);
663 return NULL;
664 }
665
666 /* Return the parameter domain of "pw".
667 */
668 __isl_give isl_set *FN(PW,params)(__isl_take PW *pw)
669 {
670 return isl_set_params(FN(PW,domain)(pw));
671 }
672
673 __isl_give isl_set *FN(PW,domain)(__isl_take PW *pw)
674 {
675 int i;
676 isl_set *dom;
677
678 if (!pw)
679 return NULL;
680
681 dom = isl_set_empty(FN(PW,get_domain_space)(pw));
682 for (i = 0; i < pw->n; ++i)
683 dom = isl_set_union_disjoint(dom, isl_set_copy(pw->p[i].set));
684
685 FN(PW,free)(pw);
686
687 return dom;
688 }
689
690 /* Exploit the equalities in the domain of piece "i" of "pw"
691 * to simplify the associated function.
692 * If the domain of piece "i" is empty, then remove it entirely,
693 * replacing it with the final piece.
694 */
695 static int FN(PW,exploit_equalities_and_remove_if_empty)(__isl_keep PW *pw,
696 int i)
697 {
698 isl_basic_set *aff;
699 int empty = isl_set_plain_is_empty(pw->p[i].set);
700
701 if (empty < 0)
702 return -1;
703 if (empty) {
704 isl_set_free(pw->p[i].set);
705 FN(EL,free)(pw->p[i].FIELD);
706 if (i != pw->n - 1)
707 pw->p[i] = pw->p[pw->n - 1];
708 pw->n--;
709
710 return 0;
711 }
712
713 aff = isl_set_affine_hull(isl_set_copy(pw->p[i].set));
714 pw->p[i].FIELD = FN(EL,substitute_equalities)(pw->p[i].FIELD, aff);
715 if (!pw->p[i].FIELD)
716 return -1;
717
718 return 0;
719 }
720
721 /* Convert a piecewise expression defined over a parameter domain
722 * into one that is defined over a zero-dimensional set.
723 */
724 __isl_give PW *FN(PW,from_range)(__isl_take PW *pw)
725 {
726 isl_space *space;
727
728 if (!pw)
729 return NULL;
730 if (!isl_space_is_set(pw->dim))
731 isl_die(FN(PW,get_ctx)(pw), isl_error_invalid,
732 "not living in a set space", return FN(PW,free)(pw));
733
734 space = FN(PW,get_space)(pw);
735 space = isl_space_from_range(space);
736 pw = FN(PW,reset_space)(pw, space);
737
738 return pw;
739 }
740
741 /* Fix the value of the given parameter or domain dimension of "pw"
742 * to be equal to "value".
743 */
744 __isl_give PW *FN(PW,fix_si)(__isl_take PW *pw, enum isl_dim_type type,
745 unsigned pos, int value)
746 {
747 int i;
748
749 if (!pw)
750 return NULL;
751
752 if (type == isl_dim_out)
753 isl_die(FN(PW,get_ctx)(pw), isl_error_invalid,
754 "cannot fix output dimension", return FN(PW,free)(pw));
755
756 if (pw->n == 0)
757 return pw;
758
759 if (type == isl_dim_in)
760 type = isl_dim_set;
761
762 pw = FN(PW,cow)(pw);
763 if (!pw)
764 return FN(PW,free)(pw);
765
766 for (i = pw->n - 1; i >= 0; --i) {
767 pw->p[i].set = isl_set_fix_si(pw->p[i].set, type, pos, value);
768 if (FN(PW,exploit_equalities_and_remove_if_empty)(pw, i) < 0)
769 return FN(PW,free)(pw);
770 }
771
772 return pw;
773 }
774
775 /* Restrict the domain of "pw" by combining each cell
776 * with "set" through a call to "fn", where "fn" may be
777 * isl_set_intersect, isl_set_intersect_params, isl_set_intersect_factor_domain,
778 * isl_set_intersect_factor_range or isl_set_subtract.
779 */
780 static __isl_give PW *FN(PW,restrict_domain)(__isl_take PW *pw,
781 __isl_take isl_set *set,
782 __isl_give isl_set *(*fn)(__isl_take isl_set *set1,
783 __isl_take isl_set *set2))
784 {
785 int i;
786
787 FN(PW,align_params_set)(&pw, &set);
788 if (!pw || !set)
789 goto error;
790
791 if (pw->n == 0) {
792 isl_set_free(set);
793 return pw;
794 }
795
796 pw = FN(PW,cow)(pw);
797 if (!pw)
798 goto error;
799
800 for (i = pw->n - 1; i >= 0; --i) {
801 pw->p[i].set = fn(pw->p[i].set, isl_set_copy(set));
802 if (FN(PW,exploit_equalities_and_remove_if_empty)(pw, i) < 0)
803 goto error;
804 }
805
806 isl_set_free(set);
807 return pw;
808 error:
809 isl_set_free(set);
810 FN(PW,free)(pw);
811 return NULL;
812 }
813
814 __isl_give PW *FN(PW,intersect_domain)(__isl_take PW *pw,
815 __isl_take isl_set *context)
816 {
817 return FN(PW,restrict_domain)(pw, context, &isl_set_intersect);
818 }
819
820 /* Intersect the domain of "pw" with the parameter domain "context".
821 */
822 __isl_give PW *FN(PW,intersect_params)(__isl_take PW *pw,
823 __isl_take isl_set *context)
824 {
825 return FN(PW,restrict_domain)(pw, context, &isl_set_intersect_params);
826 }
827
828 /* Given a piecewise expression "pw" with domain in a space [A -> B] and
829 * a set in the space A, intersect the domain with the set.
830 */
831 __isl_give PW *FN(PW,intersect_domain_wrapped_domain)(__isl_take PW *pw,
832 __isl_take isl_set *set)
833 {
834 return FN(PW,restrict_domain)(pw, set,
835 &isl_set_intersect_factor_domain);
836 }
837
838 /* Given a piecewise expression "pw" with domain in a space [A -> B] and
839 * a set in the space B, intersect the domain with the set.
840 */
841 __isl_give PW *FN(PW,intersect_domain_wrapped_range)(__isl_take PW *pw,
842 __isl_take isl_set *set)
843 {
844 return FN(PW,restrict_domain)(pw, set, &isl_set_intersect_factor_range);
845 }
846
847 /* Subtract "domain' from the domain of "pw".
848 */
849 __isl_give PW *FN(PW,subtract_domain)(__isl_take PW *pw,
850 __isl_take isl_set *domain)
851 {
852 return FN(PW,restrict_domain)(pw, domain, &isl_set_subtract);
853 }
854
855 /* Return -1 if the piece "p1" should be sorted before "p2"
856 * and 1 if it should be sorted after "p2".
857 * Return 0 if they do not need to be sorted in a specific order.
858 *
859 * The two pieces are compared on the basis of their function value expressions.
860 */
861 static int FN(PW,sort_field_cmp)(const void *p1, const void *p2, void *arg)
862 {
863 struct FN(PW,piece) const *pc1 = p1;
864 struct FN(PW,piece) const *pc2 = p2;
865
866 return FN(EL,plain_cmp)(pc1->FIELD, pc2->FIELD);
867 }
868
869 /* Sort the pieces of "pw" according to their function value
870 * expressions and then combine pairs of adjacent pieces with
871 * the same such expression.
872 *
873 * The sorting is performed in place because it does not
874 * change the meaning of "pw", but care needs to be
875 * taken not to change any possible other copies of "pw"
876 * in case anything goes wrong.
877 */
878 static __isl_give PW *FN(PW,sort_unique)(__isl_take PW *pw)
879 {
880 int i, j;
881 isl_set *set;
882
883 if (!pw)
884 return NULL;
885 if (pw->n <= 1)
886 return pw;
887 if (isl_sort(pw->p, pw->n, sizeof(pw->p[0]),
888 &FN(PW,sort_field_cmp), NULL) < 0)
889 return FN(PW,free)(pw);
890 for (i = pw->n - 1; i >= 1; --i) {
891 if (!FN(EL,plain_is_equal)(pw->p[i - 1].FIELD, pw->p[i].FIELD))
892 continue;
893 set = isl_set_union(isl_set_copy(pw->p[i - 1].set),
894 isl_set_copy(pw->p[i].set));
895 if (!set)
896 return FN(PW,free)(pw);
897 isl_set_free(pw->p[i].set);
898 FN(EL,free)(pw->p[i].FIELD);
899 isl_set_free(pw->p[i - 1].set);
900 pw->p[i - 1].set = set;
901 for (j = i + 1; j < pw->n; ++j)
902 pw->p[j - 1] = pw->p[j];
903 pw->n--;
904 }
905
906 return pw;
907 }
908
909 /* Compute the gist of "pw" with respect to the domain constraints
910 * of "context" for the case where the domain of the last element
911 * of "pw" is equal to "context".
912 * Call "fn_el" to compute the gist of this element, replace
913 * its domain by the universe and drop all other elements
914 * as their domains are necessarily disjoint from "context".
915 */
916 static __isl_give PW *FN(PW,gist_last)(__isl_take PW *pw,
917 __isl_take isl_set *context,
918 __isl_give EL *(*fn_el)(__isl_take EL *el, __isl_take isl_set *set))
919 {
920 int i;
921 isl_space *space;
922
923 for (i = 0; i < pw->n - 1; ++i) {
924 isl_set_free(pw->p[i].set);
925 FN(EL,free)(pw->p[i].FIELD);
926 }
927 pw->p[0].FIELD = pw->p[pw->n - 1].FIELD;
928 pw->p[0].set = pw->p[pw->n - 1].set;
929 pw->n = 1;
930
931 space = isl_set_get_space(context);
932 pw->p[0].FIELD = fn_el(pw->p[0].FIELD, context);
933 context = isl_set_universe(space);
934 isl_set_free(pw->p[0].set);
935 pw->p[0].set = context;
936
937 if (!pw->p[0].FIELD || !pw->p[0].set)
938 return FN(PW,free)(pw);
939
940 return pw;
941 }
942
943 /* Compute the gist of "pw" with respect to the domain constraints
944 * of "context". Call "fn_el" to compute the gist of the elements
945 * and "fn_dom" to compute the gist of the domains.
946 *
947 * If the piecewise expression is empty or the context is the universe,
948 * then nothing can be simplified.
949 * If "pw" has a single domain and it is equal to "context",
950 * then simply replace the domain by the universe.
951 * Combine duplicate function value expressions first
952 * to increase the chance of "pw" having a single domain.
953 */
954 static __isl_give PW *FN(PW,gist_fn)(__isl_take PW *pw,
955 __isl_take isl_set *context,
956 __isl_give EL *(*fn_el)(__isl_take EL *el,
957 __isl_take isl_set *set),
958 __isl_give isl_set *(*fn_dom)(__isl_take isl_set *set,
959 __isl_take isl_basic_set *bset))
960 {
961 int i;
962 int is_universe;
963 isl_basic_set *hull = NULL;
964
965 pw = FN(PW,sort_unique)(pw);
966 if (!pw || !context)
967 goto error;
968
969 if (pw->n == 0) {
970 isl_set_free(context);
971 return pw;
972 }
973
974 is_universe = isl_set_plain_is_universe(context);
975 if (is_universe < 0)
976 goto error;
977 if (is_universe) {
978 isl_set_free(context);
979 return pw;
980 }
981
982 FN(PW,align_params_set)(&pw, &context);
983
984 pw = FN(PW,cow)(pw);
985 if (!pw)
986 goto error;
987
988 if (pw->n == 1) {
989 int equal;
990
991 equal = isl_set_plain_is_equal(pw->p[0].set, context);
992 if (equal < 0)
993 goto error;
994 if (equal)
995 return FN(PW,gist_last)(pw, context, fn_el);
996 }
997
998 context = isl_set_compute_divs(context);
999 hull = isl_set_simple_hull(isl_set_copy(context));
1000
1001 for (i = pw->n - 1; i >= 0; --i) {
1002 isl_set *set_i;
1003 int empty;
1004
1005 if (i == pw->n - 1) {
1006 int equal;
1007 equal = isl_set_plain_is_equal(pw->p[i].set, context);
1008 if (equal < 0)
1009 goto error;
1010 if (equal) {
1011 isl_basic_set_free(hull);
1012 return FN(PW,gist_last)(pw, context, fn_el);
1013 }
1014 }
1015 set_i = isl_set_intersect(isl_set_copy(pw->p[i].set),
1016 isl_set_copy(context));
1017 empty = isl_set_plain_is_empty(set_i);
1018 pw->p[i].FIELD = fn_el(pw->p[i].FIELD, set_i);
1019 pw->p[i].set = fn_dom(pw->p[i].set, isl_basic_set_copy(hull));
1020 if (empty < 0 || !pw->p[i].FIELD || !pw->p[i].set)
1021 goto error;
1022 if (empty) {
1023 isl_set_free(pw->p[i].set);
1024 FN(EL,free)(pw->p[i].FIELD);
1025 if (i != pw->n - 1)
1026 pw->p[i] = pw->p[pw->n - 1];
1027 pw->n--;
1028 }
1029 }
1030
1031 isl_basic_set_free(hull);
1032 isl_set_free(context);
1033
1034 return pw;
1035 error:
1036 FN(PW,free)(pw);
1037 isl_basic_set_free(hull);
1038 isl_set_free(context);
1039 return NULL;
1040 }
1041
1042 __isl_give PW *FN(PW,gist)(__isl_take PW *pw, __isl_take isl_set *context)
1043 {
1044 return FN(PW,gist_fn)(pw, context, &FN(EL,gist),
1045 &isl_set_gist_basic_set);
1046 }
1047
1048 __isl_give PW *FN(PW,gist_params)(__isl_take PW *pw,
1049 __isl_take isl_set *context)
1050 {
1051 return FN(PW,gist_fn)(pw, context, &FN(EL,gist_params),
1052 &isl_set_gist_params_basic_set);
1053 }
1054
1055 /* Coalesce the domains of "pw".
1056 *
1057 * Prior to the actual coalescing, first sort the pieces such that
1058 * pieces with the same function value expression are combined
1059 * into a single piece, the combined domain of which can then
1060 * be coalesced.
1061 */
1062 __isl_give PW *FN(PW,coalesce)(__isl_take PW *pw)
1063 {
1064 int i;
1065
1066 pw = FN(PW,sort_unique)(pw);
1067 if (!pw)
1068 return NULL;
1069
1070 for (i = 0; i < pw->n; ++i) {
1071 pw->p[i].set = isl_set_coalesce(pw->p[i].set);
1072 if (!pw->p[i].set)
1073 goto error;
1074 }
1075
1076 return pw;
1077 error:
1078 FN(PW,free)(pw);
1079 return NULL;
1080 }
1081
1082 isl_ctx *FN(PW,get_ctx)(__isl_keep PW *pw)
1083 {
1084 return pw ? isl_space_get_ctx(pw->dim) : NULL;
1085 }
1086
1087 isl_bool FN(PW,involves_dims)(__isl_keep PW *pw, enum isl_dim_type type,
1088 unsigned first, unsigned n)
1089 {
1090 int i;
1091 enum isl_dim_type set_type;
1092
1093 if (!pw)
1094 return isl_bool_error;
1095 if (pw->n == 0 || n == 0)
1096 return isl_bool_false;
1097
1098 set_type = type == isl_dim_in ? isl_dim_set : type;
1099
1100 for (i = 0; i < pw->n; ++i) {
1101 isl_bool involves = FN(EL,involves_dims)(pw->p[i].FIELD,
1102 type, first, n);
1103 if (involves < 0 || involves)
1104 return involves;
1105 involves = isl_set_involves_dims(pw->p[i].set,
1106 set_type, first, n);
1107 if (involves < 0 || involves)
1108 return involves;
1109 }
1110 return isl_bool_false;
1111 }
1112
1113 __isl_give PW *FN(PW,set_dim_name)(__isl_take PW *pw,
1114 enum isl_dim_type type, unsigned pos, const char *s)
1115 {
1116 int i;
1117 enum isl_dim_type set_type;
1118
1119 pw = FN(PW,cow)(pw);
1120 if (!pw)
1121 return NULL;
1122
1123 set_type = type == isl_dim_in ? isl_dim_set : type;
1124
1125 pw->dim = isl_space_set_dim_name(pw->dim, type, pos, s);
1126 if (!pw->dim)
1127 goto error;
1128
1129 for (i = 0; i < pw->n; ++i) {
1130 pw->p[i].set = isl_set_set_dim_name(pw->p[i].set,
1131 set_type, pos, s);
1132 if (!pw->p[i].set)
1133 goto error;
1134 pw->p[i].FIELD = FN(EL,set_dim_name)(pw->p[i].FIELD, type, pos, s);
1135 if (!pw->p[i].FIELD)
1136 goto error;
1137 }
1138
1139 return pw;
1140 error:
1141 FN(PW,free)(pw);
1142 return NULL;
1143 }
1144
1145 __isl_give PW *FN(PW,drop_dims)(__isl_take PW *pw,
1146 enum isl_dim_type type, unsigned first, unsigned n)
1147 {
1148 int i;
1149 enum isl_dim_type set_type;
1150
1151 if (!pw)
1152 return NULL;
1153 if (n == 0 && !isl_space_get_tuple_name(pw->dim, type))
1154 return pw;
1155
1156 set_type = type == isl_dim_in ? isl_dim_set : type;
1157
1158 pw = FN(PW,cow)(pw);
1159 if (!pw)
1160 return NULL;
1161 pw->dim = isl_space_drop_dims(pw->dim, type, first, n);
1162 if (!pw->dim)
1163 goto error;
1164 for (i = 0; i < pw->n; ++i) {
1165 pw->p[i].FIELD = FN(EL,drop_dims)(pw->p[i].FIELD, type, first, n);
1166 if (!pw->p[i].FIELD)
1167 goto error;
1168 if (type == isl_dim_out)
1169 continue;
1170 pw->p[i].set = isl_set_drop(pw->p[i].set, set_type, first, n);
1171 if (!pw->p[i].set)
1172 goto error;
1173 }
1174
1175 return pw;
1176 error:
1177 FN(PW,free)(pw);
1178 return NULL;
1179 }
1180
1181 /* This function is very similar to drop_dims.
1182 * The only difference is that the cells may still involve
1183 * the specified dimensions. They are removed using
1184 * isl_set_project_out instead of isl_set_drop.
1185 */
1186 __isl_give PW *FN(PW,project_out)(__isl_take PW *pw,
1187 enum isl_dim_type type, unsigned first, unsigned n)
1188 {
1189 int i;
1190 enum isl_dim_type set_type;
1191
1192 if (!pw)
1193 return NULL;
1194 if (n == 0 && !isl_space_get_tuple_name(pw->dim, type))
1195 return pw;
1196
1197 set_type = type == isl_dim_in ? isl_dim_set : type;
1198
1199 pw = FN(PW,cow)(pw);
1200 if (!pw)
1201 return NULL;
1202 pw->dim = isl_space_drop_dims(pw->dim, type, first, n);
1203 if (!pw->dim)
1204 goto error;
1205 for (i = 0; i < pw->n; ++i) {
1206 pw->p[i].set = isl_set_project_out(pw->p[i].set,
1207 set_type, first, n);
1208 if (!pw->p[i].set)
1209 goto error;
1210 pw->p[i].FIELD = FN(EL,drop_dims)(pw->p[i].FIELD, type, first, n);
1211 if (!pw->p[i].FIELD)
1212 goto error;
1213 }
1214
1215 return pw;
1216 error:
1217 FN(PW,free)(pw);
1218 return NULL;
1219 }
1220
1221 /* Project the domain of pw onto its parameter space.
1222 */
1223 __isl_give PW *FN(PW,project_domain_on_params)(__isl_take PW *pw)
1224 {
1225 isl_space *space;
1226 isl_size n;
1227
1228 n = FN(PW,dim)(pw, isl_dim_in);
1229 if (n < 0)
1230 return FN(PW,free)(pw);
1231 pw = FN(PW,project_out)(pw, isl_dim_in, 0, n);
1232 space = FN(PW,get_domain_space)(pw);
1233 space = isl_space_params(space);
1234 pw = FN(PW,reset_domain_space)(pw, space);
1235 return pw;
1236 }
1237
1238 /* Drop all parameters not referenced by "pw".
1239 */
1240 __isl_give PW *FN(PW,drop_unused_params)(__isl_take PW *pw)
1241 {
1242 isl_size n;
1243 int i;
1244
1245 if (FN(PW,check_named_params)(pw) < 0)
1246 return FN(PW,free)(pw);
1247
1248 n = FN(PW,dim)(pw, isl_dim_param);
1249 if (n < 0)
1250 return FN(PW,free)(pw);
1251 for (i = n - 1; i >= 0; i--) {
1252 isl_bool involves;
1253
1254 involves = FN(PW,involves_dims)(pw, isl_dim_param, i, 1);
1255 if (involves < 0)
1256 return FN(PW,free)(pw);
1257 if (!involves)
1258 pw = FN(PW,drop_dims)(pw, isl_dim_param, i, 1);
1259 }
1260
1261 return pw;
1262 }
1263
1264 __isl_give PW *FN(PW,fix_dim)(__isl_take PW *pw,
1265 enum isl_dim_type type, unsigned pos, isl_int v)
1266 {
1267 int i;
1268
1269 if (!pw)
1270 return NULL;
1271
1272 if (type == isl_dim_in)
1273 type = isl_dim_set;
1274
1275 pw = FN(PW,cow)(pw);
1276 if (!pw)
1277 return NULL;
1278 for (i = 0; i < pw->n; ++i) {
1279 pw->p[i].set = isl_set_fix(pw->p[i].set, type, pos, v);
1280 if (FN(PW,exploit_equalities_and_remove_if_empty)(pw, i) < 0)
1281 return FN(PW,free)(pw);
1282 }
1283
1284 return pw;
1285 }
1286
1287 /* Fix the value of the variable at position "pos" of type "type" of "pw"
1288 * to be equal to "v".
1289 */
1290 __isl_give PW *FN(PW,fix_val)(__isl_take PW *pw,
1291 enum isl_dim_type type, unsigned pos, __isl_take isl_val *v)
1292 {
1293 if (!v)
1294 return FN(PW,free)(pw);
1295 if (!isl_val_is_int(v))
1296 isl_die(FN(PW,get_ctx)(pw), isl_error_invalid,
1297 "expecting integer value", goto error);
1298
1299 pw = FN(PW,fix_dim)(pw, type, pos, v->n);
1300 isl_val_free(v);
1301
1302 return pw;
1303 error:
1304 isl_val_free(v);
1305 return FN(PW,free)(pw);
1306 }
1307
1308 isl_size FN(PW,dim)(__isl_keep PW *pw, enum isl_dim_type type)
1309 {
1310 return isl_space_dim(FN(PW,peek_space)(pw), type);
1311 }
1312
1313 __isl_give PW *FN(PW,split_dims)(__isl_take PW *pw,
1314 enum isl_dim_type type, unsigned first, unsigned n)
1315 {
1316 int i;
1317
1318 if (!pw)
1319 return NULL;
1320 if (n == 0)
1321 return pw;
1322
1323 if (type == isl_dim_in)
1324 type = isl_dim_set;
1325
1326 pw = FN(PW,cow)(pw);
1327 if (!pw)
1328 return NULL;
1329 if (!pw->dim)
1330 goto error;
1331 for (i = 0; i < pw->n; ++i) {
1332 pw->p[i].set = isl_set_split_dims(pw->p[i].set, type, first, n);
1333 if (!pw->p[i].set)
1334 goto error;
1335 }
1336
1337 return pw;
1338 error:
1339 FN(PW,free)(pw);
1340 return NULL;
1341 }
1342
1343 /* Return the space of "pw".
1344 */
1345 __isl_keep isl_space *FN(PW,peek_space)(__isl_keep PW *pw)
1346 {
1347 return pw ? pw->dim : NULL;
1348 }
1349
1350 __isl_give isl_space *FN(PW,get_space)(__isl_keep PW *pw)
1351 {
1352 return isl_space_copy(FN(PW,peek_space)(pw));
1353 }
1354
1355 /* Return the space of "pw".
1356 * This may be either a copy or the space itself
1357 * if there is only one reference to "pw".
1358 * This allows the space to be modified inplace
1359 * if both the piecewise expression and its space have only a single reference.
1360 * The caller is not allowed to modify "pw" between this call and
1361 * a subsequent call to isl_pw_*_restore_*.
1362 * The only exception is that isl_pw_*_free can be called instead.
1363 */
1364 __isl_give isl_space *FN(PW,take_space)(__isl_keep PW *pw)
1365 {
1366 isl_space *space;
1367
1368 if (!pw)
1369 return NULL;
1370 if (pw->ref != 1)
1371 return FN(PW,get_space)(pw);
1372 space = pw->dim;
1373 pw->dim = NULL;
1374 return space;
1375 }
1376
1377 /* Set the space of "pw" to "space", where the space of "pw" may be missing
1378 * due to a preceding call to isl_pw_*_take_space.
1379 * However, in this case, "pw" only has a single reference and
1380 * then the call to isl_pw_*_cow has no effect.
1381 */
1382 __isl_give PW *FN(PW,restore_space)(__isl_take PW *pw,
1383 __isl_take isl_space *space)
1384 {
1385 if (!pw || !space)
1386 goto error;
1387
1388 if (pw->dim == space) {
1389 isl_space_free(space);
1390 return pw;
1391 }
1392
1393 pw = FN(PW,cow)(pw);
1394 if (!pw)
1395 goto error;
1396 isl_space_free(pw->dim);
1397 pw->dim = space;
1398
1399 return pw;
1400 error:
1401 FN(PW,free)(pw);
1402 isl_space_free(space);
1403 return NULL;
1404 }
1405
1406 /* Check that "pos" is a valid position for a cell in "pw".
1407 */
1408 static isl_stat FN(PW,check_pos)(__isl_keep PW *pw, int pos)
1409 {
1410 if (!pw)
1411 return isl_stat_error;
1412 if (pos < 0 || pos >= pw->n)
1413 isl_die(FN(PW,get_ctx)(pw), isl_error_internal,
1414 "position out of bounds", return isl_stat_error);
1415 return isl_stat_ok;
1416 }
1417
1418 /* Return the cell at position "pos" in "pw".
1419 */
1420 static __isl_keep isl_set *FN(PW,peek_domain_at)(__isl_keep PW *pw, int pos)
1421 {
1422 if (FN(PW,check_pos)(pw, pos) < 0)
1423 return NULL;
1424 return pw->p[pos].set;
1425 }
1426
1427 /* Return a copy of the cell at position "pos" in "pw".
1428 */
1429 __isl_give isl_set *FN(PW,get_domain_at)(__isl_keep PW *pw, int pos)
1430 {
1431 return isl_set_copy(FN(PW,peek_domain_at)(pw, pos));
1432 }
1433
1434 /* Return the base expression associated to
1435 * the cell at position "pos" in "pw".
1436 */
1437 static __isl_keep EL *FN(PW,peek_base_at)(__isl_keep PW *pw, int pos)
1438 {
1439 if (FN(PW,check_pos)(pw, pos) < 0)
1440 return NULL;
1441 return pw->p[pos].FIELD;
1442 }
1443
1444 /* Return a copy of the base expression associated to
1445 * the cell at position "pos" in "pw".
1446 */
1447 __isl_give EL *FN(PW,get_base_at)(__isl_keep PW *pw, int pos)
1448 {
1449 return FN(EL,copy)(FN(PW,peek_base_at)(pw, pos));
1450 }
1451
1452 /* Return the base expression associated to
1453 * the cell at position "pos" in "pw".
1454 * This may be either a copy or the base expression itself
1455 * if there is only one reference to "pw".
1456 * This allows the base expression to be modified inplace
1457 * if both the piecewise expression and this base expression
1458 * have only a single reference.
1459 * The caller is not allowed to modify "pw" between this call and
1460 * a subsequent call to isl_pw_*_restore_*.
1461 * The only exception is that isl_pw_*_free can be called instead.
1462 */
1463 __isl_give EL *FN(PW,take_base_at)(__isl_keep PW *pw, int pos)
1464 {
1465 EL *el;
1466
1467 if (!pw)
1468 return NULL;
1469 if (pw->ref != 1)
1470 return FN(PW,get_base_at)(pw, pos);
1471 if (FN(PW,check_pos)(pw, pos) < 0)
1472 return NULL;
1473 el = pw->p[pos].FIELD;
1474 pw->p[pos].FIELD = NULL;
1475 return el;
1476 }
1477
1478 /* Set the base expression associated to
1479 * the cell at position "pos" in "pw" to "el",
1480 * where this base expression may be missing
1481 * due to a preceding call to isl_pw_*_take_base_at.
1482 * However, in this case, "pw" only has a single reference and
1483 * then the call to isl_pw_*_cow has no effect.
1484 */
1485 __isl_give PW *FN(PW,restore_base_at)(__isl_take PW *pw, int pos,
1486 __isl_take EL *el)
1487 {
1488 if (FN(PW,check_pos)(pw, pos) < 0 || !el)
1489 goto error;
1490
1491 if (pw->p[pos].FIELD == el) {
1492 FN(EL,free)(el);
1493 return pw;
1494 }
1495
1496 pw = FN(PW,cow)(pw);
1497 if (!pw)
1498 goto error;
1499 FN(EL,free)(pw->p[pos].FIELD);
1500 pw->p[pos].FIELD = el;
1501
1502 return pw;
1503 error:
1504 FN(PW,free)(pw);
1505 FN(EL,free)(el);
1506 return NULL;
1507 }
1508
1509 __isl_give isl_space *FN(PW,get_domain_space)(__isl_keep PW *pw)
1510 {
1511 return pw ? isl_space_domain(isl_space_copy(pw->dim)) : NULL;
1512 }
1513
1514 /* Return the position of the dimension of the given type and name
1515 * in "pw".
1516 * Return -1 if no such dimension can be found.
1517 */
1518 int FN(PW,find_dim_by_name)(__isl_keep PW *pw,
1519 enum isl_dim_type type, const char *name)
1520 {
1521 if (!pw)
1522 return -1;
1523 return isl_space_find_dim_by_name(pw->dim, type, name);
1524 }
1525
1526 /* Return the position of the dimension of the given type and identifier
1527 * in "pw".
1528 * Return -1 if no such dimension can be found.
1529 */
1530 static int FN(PW,find_dim_by_id)(__isl_keep PW *pw,
1531 enum isl_dim_type type, __isl_keep isl_id *id)
1532 {
1533 isl_space *space;
1534
1535 space = FN(PW,peek_space)(pw);
1536 return isl_space_find_dim_by_id(space, type, id);
1537 }
1538
1539 /* Does the piecewise expression "pw" depend in any way
1540 * on the parameter with identifier "id"?
1541 */
1542 isl_bool FN(PW,involves_param_id)(__isl_keep PW *pw, __isl_keep isl_id *id)
1543 {
1544 int pos;
1545
1546 if (!pw || !id)
1547 return isl_bool_error;
1548 if (pw->n == 0)
1549 return isl_bool_false;
1550
1551 pos = FN(PW,find_dim_by_id)(pw, isl_dim_param, id);
1552 if (pos < 0)
1553 return isl_bool_false;
1554 return FN(PW,involves_dims)(pw, isl_dim_param, pos, 1);
1555 }
1556
1557 /* Reset the space of "pw". Since we don't know if the elements
1558 * represent the spaces themselves or their domains, we pass along
1559 * both when we call their reset_space_and_domain.
1560 */
1561 static __isl_give PW *FN(PW,reset_space_and_domain)(__isl_take PW *pw,
1562 __isl_take isl_space *space, __isl_take isl_space *domain)
1563 {
1564 int i;
1565
1566 pw = FN(PW,cow)(pw);
1567 if (!pw || !space || !domain)
1568 goto error;
1569
1570 for (i = 0; i < pw->n; ++i) {
1571 pw->p[i].set = isl_set_reset_space(pw->p[i].set,
1572 isl_space_copy(domain));
1573 if (!pw->p[i].set)
1574 goto error;
1575 pw->p[i].FIELD = FN(EL,reset_space_and_domain)(pw->p[i].FIELD,
1576 isl_space_copy(space), isl_space_copy(domain));
1577 if (!pw->p[i].FIELD)
1578 goto error;
1579 }
1580
1581 isl_space_free(domain);
1582
1583 isl_space_free(pw->dim);
1584 pw->dim = space;
1585
1586 return pw;
1587 error:
1588 isl_space_free(domain);
1589 isl_space_free(space);
1590 FN(PW,free)(pw);
1591 return NULL;
1592 }
1593
1594 __isl_give PW *FN(PW,reset_domain_space)(__isl_take PW *pw,
1595 __isl_take isl_space *domain)
1596 {
1597 isl_space *space;
1598
1599 space = isl_space_extend_domain_with_range(isl_space_copy(domain),
1600 FN(PW,get_space)(pw));
1601 return FN(PW,reset_space_and_domain)(pw, space, domain);
1602 }
1603
1604 __isl_give PW *FN(PW,reset_space)(__isl_take PW *pw,
1605 __isl_take isl_space *space)
1606 {
1607 isl_space *domain;
1608
1609 domain = isl_space_domain(isl_space_copy(space));
1610 return FN(PW,reset_space_and_domain)(pw, space, domain);
1611 }
1612
1613 __isl_give PW *FN(PW,set_tuple_id)(__isl_take PW *pw, enum isl_dim_type type,
1614 __isl_take isl_id *id)
1615 {
1616 isl_space *space;
1617
1618 pw = FN(PW,cow)(pw);
1619 if (!pw)
1620 goto error;
1621
1622 space = FN(PW,get_space)(pw);
1623 space = isl_space_set_tuple_id(space, type, id);
1624
1625 return FN(PW,reset_space)(pw, space);
1626 error:
1627 isl_id_free(id);
1628 return FN(PW,free)(pw);
1629 }
1630
1631 /* Drop the id on the specified tuple.
1632 */
1633 __isl_give PW *FN(PW,reset_tuple_id)(__isl_take PW *pw, enum isl_dim_type type)
1634 {
1635 isl_space *space;
1636
1637 if (!pw)
1638 return NULL;
1639 if (!FN(PW,has_tuple_id)(pw, type))
1640 return pw;
1641
1642 pw = FN(PW,cow)(pw);
1643 if (!pw)
1644 return NULL;
1645
1646 space = FN(PW,get_space)(pw);
1647 space = isl_space_reset_tuple_id(space, type);
1648
1649 return FN(PW,reset_space)(pw, space);
1650 }
1651
1652 __isl_give PW *FN(PW,set_dim_id)(__isl_take PW *pw,
1653 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
1654 {
1655 pw = FN(PW,cow)(pw);
1656 if (!pw)
1657 goto error;
1658 pw->dim = isl_space_set_dim_id(pw->dim, type, pos, id);
1659 return FN(PW,reset_space)(pw, isl_space_copy(pw->dim));
1660 error:
1661 isl_id_free(id);
1662 return FN(PW,free)(pw);
1663 }
1664
1665 /* Reset the user pointer on all identifiers of parameters and tuples
1666 * of the space of "pw".
1667 */
1668 __isl_give PW *FN(PW,reset_user)(__isl_take PW *pw)
1669 {
1670 isl_space *space;
1671
1672 space = FN(PW,get_space)(pw);
1673 space = isl_space_reset_user(space);
1674
1675 return FN(PW,reset_space)(pw, space);
1676 }
1677
1678 isl_size FN(PW,n_piece)(__isl_keep PW *pw)
1679 {
1680 return pw ? pw->n : isl_size_error;
1681 }
1682
1683 isl_stat FN(PW,foreach_piece)(__isl_keep PW *pw,
1684 isl_stat (*fn)(__isl_take isl_set *set, __isl_take EL *el, void *user),
1685 void *user)
1686 {
1687 int i;
1688
1689 if (!pw)
1690 return isl_stat_error;
1691
1692 for (i = 0; i < pw->n; ++i)
1693 if (fn(isl_set_copy(pw->p[i].set),
1694 FN(EL,copy)(pw->p[i].FIELD), user) < 0)
1695 return isl_stat_error;
1696
1697 return isl_stat_ok;
1698 }
1699
1700 /* Does "test" succeed on every cell of "pw"?
1701 */
1702 isl_bool FN(PW,every_piece)(__isl_keep PW *pw,
1703 isl_bool (*test)(__isl_keep isl_set *set,
1704 __isl_keep EL *el, void *user), void *user)
1705 {
1706 int i;
1707
1708 if (!pw)
1709 return isl_bool_error;
1710
1711 for (i = 0; i < pw->n; ++i) {
1712 isl_bool r;
1713
1714 r = test(pw->p[i].set, pw->p[i].FIELD, user);
1715 if (r < 0 || !r)
1716 return r;
1717 }
1718
1719 return isl_bool_true;
1720 }
1721
1722 /* Is "pw" defined over a single universe domain?
1723 *
1724 * If the default value of this piecewise type is zero,
1725 * then a "pw" with a zero number of cells is also accepted
1726 * as it represents the default zero value.
1727 */
1728 isl_bool FN(FN(PW,isa),BASE)(__isl_keep PW *pw)
1729 {
1730 isl_size n;
1731
1732 n = FN(PW,n_piece)(pw);
1733 if (n < 0)
1734 return isl_bool_error;
1735 if (DEFAULT_IS_ZERO && n == 0)
1736 return isl_bool_true;
1737 if (n != 1)
1738 return isl_bool_false;
1739 return isl_set_plain_is_universe(FN(PW,peek_domain_at)(pw, 0));
1740 }
1741
1742 /* Return a zero base expression in the same space (and of the same type)
1743 * as "pw".
1744 */
1745 static __isl_give EL *FN(EL,zero_like_type)(__isl_take PW *pw OPT_TYPE_PARAM)
1746 {
1747 isl_space *space;
1748
1749 space = FN(PW,get_space)(pw);
1750 FN(PW,free)(pw);
1751 return FN(EL,zero_in_space)(space OPT_TYPE_ARG(NO_LOC));
1752 }
1753
1754 #ifndef HAS_TYPE
1755 /* Return a zero base expression in the same space as "pw".
1756 */
1757 static __isl_give EL *FN(EL,zero_like)(__isl_take PW *pw)
1758 {
1759 return FN(EL,zero_like_type)(pw);
1760 }
1761 #else
1762 /* Return a zero base expression in the same space and of the same type
1763 * as "pw".
1764 *
1765 * Pass along the type as an explicit argument for uniform handling
1766 * in isl_*_zero_like_type.
1767 */
1768 static __isl_give EL *FN(EL,zero_like)(__isl_take PW *pw)
1769 {
1770 enum isl_fold type;
1771
1772 type = FN(PW,get_type)(pw);
1773 if (type < 0)
1774 goto error;
1775 return FN(EL,zero_like_type)(pw, type);
1776 error:
1777 FN(PW,free)(pw);
1778 return NULL;
1779 }
1780 #endif
1781
1782 /* Given that "pw" is defined over a single universe domain,
1783 * return the base expression associated to this domain.
1784 *
1785 * If the number of cells is zero, then "pw" is of a piecewise type
1786 * with a default zero value and effectively represents zero.
1787 * In this case, create a zero base expression in the same space
1788 * (and with the same type).
1789 * Otherwise, simply extract the associated base expression.
1790 */
1791 __isl_give EL *FN(FN(PW,as),BASE)(__isl_take PW *pw)
1792 {
1793 isl_bool is_total;
1794 isl_size n;
1795 EL *el;
1796
1797 is_total = FN(FN(PW,isa),BASE)(pw);
1798 if (is_total < 0)
1799 goto error;
1800 if (!is_total)
1801 isl_die(FN(PW,get_ctx)(pw), isl_error_invalid,
1802 "expecting single total function", goto error);
1803 n = FN(PW,n_piece)(pw);
1804 if (n < 0)
1805 goto error;
1806 if (n == 0)
1807 return FN(EL,zero_like)(pw);
1808 el = FN(PW,take_base_at)(pw, 0);
1809 FN(PW,free)(pw);
1810 return el;
1811 error:
1812 FN(PW,free)(pw);
1813 return NULL;
1814 }
1815
1816 #ifdef HAS_TYPE
1817 /* Negate the type of "pw".
1818 */
1819 static __isl_give PW *FN(PW,negate_type)(__isl_take PW *pw)
1820 {
1821 pw = FN(PW,cow)(pw);
1822 if (!pw)
1823 return NULL;
1824 pw->type = isl_fold_type_negate(pw->type);
1825 return pw;
1826 }
1827 #else
1828 /* Negate the type of "pw".
1829 * Since "pw" does not have a type, do nothing.
1830 */
1831 static __isl_give PW *FN(PW,negate_type)(__isl_take PW *pw)
1832 {
1833 return pw;
1834 }
1835 #endif
1836
1837 __isl_give PW *FN(PW,mul_isl_int)(__isl_take PW *pw, isl_int v)
1838 {
1839 int i;
1840
1841 if (isl_int_is_one(v))
1842 return pw;
1843 if (pw && DEFAULT_IS_ZERO && isl_int_is_zero(v)) {
1844 PW *zero;
1845 isl_space *space = FN(PW,get_space)(pw);
1846 zero = FN(PW,ZERO)(space OPT_TYPE_ARG(pw->));
1847 FN(PW,free)(pw);
1848 return zero;
1849 }
1850 pw = FN(PW,cow)(pw);
1851 if (isl_int_is_neg(v))
1852 pw = FN(PW,negate_type)(pw);
1853 if (!pw)
1854 return NULL;
1855 if (pw->n == 0)
1856 return pw;
1857
1858 for (i = 0; i < pw->n; ++i) {
1859 pw->p[i].FIELD = FN(EL,scale)(pw->p[i].FIELD, v);
1860 if (!pw->p[i].FIELD)
1861 goto error;
1862 }
1863
1864 return pw;
1865 error:
1866 FN(PW,free)(pw);
1867 return NULL;
1868 }
1869
1870 /* Multiply the pieces of "pw" by "v" and return the result.
1871 */
1872 __isl_give PW *FN(PW,scale_val)(__isl_take PW *pw, __isl_take isl_val *v)
1873 {
1874 int i;
1875
1876 if (!pw || !v)
1877 goto error;
1878
1879 if (isl_val_is_one(v)) {
1880 isl_val_free(v);
1881 return pw;
1882 }
1883 if (pw && DEFAULT_IS_ZERO && isl_val_is_zero(v)) {
1884 PW *zero;
1885 isl_space *space = FN(PW,get_space)(pw);
1886 zero = FN(PW,ZERO)(space OPT_TYPE_ARG(pw->));
1887 FN(PW,free)(pw);
1888 isl_val_free(v);
1889 return zero;
1890 }
1891 if (pw->n == 0) {
1892 isl_val_free(v);
1893 return pw;
1894 }
1895 pw = FN(PW,cow)(pw);
1896 if (isl_val_is_neg(v))
1897 pw = FN(PW,negate_type)(pw);
1898 if (!pw)
1899 goto error;
1900
1901 for (i = 0; i < pw->n; ++i) {
1902 pw->p[i].FIELD = FN(EL,scale_val)(pw->p[i].FIELD,
1903 isl_val_copy(v));
1904 if (!pw->p[i].FIELD)
1905 goto error;
1906 }
1907
1908 isl_val_free(v);
1909 return pw;
1910 error:
1911 isl_val_free(v);
1912 FN(PW,free)(pw);
1913 return NULL;
1914 }
1915
1916 /* Divide the pieces of "pw" by "v" and return the result.
1917 */
1918 __isl_give PW *FN(PW,scale_down_val)(__isl_take PW *pw, __isl_take isl_val *v)
1919 {
1920 int i;
1921
1922 if (!pw || !v)
1923 goto error;
1924
1925 if (isl_val_is_one(v)) {
1926 isl_val_free(v);
1927 return pw;
1928 }
1929
1930 if (!isl_val_is_rat(v))
1931 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1932 "expecting rational factor", goto error);
1933 if (isl_val_is_zero(v))
1934 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1935 "cannot scale down by zero", goto error);
1936
1937 if (pw->n == 0) {
1938 isl_val_free(v);
1939 return pw;
1940 }
1941 pw = FN(PW,cow)(pw);
1942 if (isl_val_is_neg(v))
1943 pw = FN(PW,negate_type)(pw);
1944 if (!pw)
1945 goto error;
1946
1947 for (i = 0; i < pw->n; ++i) {
1948 pw->p[i].FIELD = FN(EL,scale_down_val)(pw->p[i].FIELD,
1949 isl_val_copy(v));
1950 if (!pw->p[i].FIELD)
1951 goto error;
1952 }
1953
1954 isl_val_free(v);
1955 return pw;
1956 error:
1957 isl_val_free(v);
1958 FN(PW,free)(pw);
1959 return NULL;
1960 }
1961
1962 __isl_give PW *FN(PW,scale)(__isl_take PW *pw, isl_int v)
1963 {
1964 return FN(PW,mul_isl_int)(pw, v);
1965 }
1966
1967 /* Apply some normalization to "pw".
1968 * In particular, sort the pieces according to their function value
1969 * expressions, combining pairs of adjacent pieces with
1970 * the same such expression, and then normalize the domains of the pieces.
1971 *
1972 * We normalize in place, but if anything goes wrong we need
1973 * to return NULL, so we need to make sure we don't change the
1974 * meaning of any possible other copies of "pw".
1975 */
1976 __isl_give PW *FN(PW,normalize)(__isl_take PW *pw)
1977 {
1978 int i;
1979 isl_set *set;
1980
1981 pw = FN(PW,sort_unique)(pw);
1982 if (!pw)
1983 return NULL;
1984 for (i = 0; i < pw->n; ++i) {
1985 set = isl_set_normalize(isl_set_copy(pw->p[i].set));
1986 if (!set)
1987 return FN(PW,free)(pw);
1988 isl_set_free(pw->p[i].set);
1989 pw->p[i].set = set;
1990 }
1991
1992 return pw;
1993 }
1994
1995 /* Is pw1 obviously equal to pw2?
1996 * That is, do they have obviously identical cells and obviously identical
1997 * elements on each cell?
1998 *
1999 * If "pw1" or "pw2" contain any NaNs, then they are considered
2000 * not to be the same. A NaN is not equal to anything, not even
2001 * to another NaN.
2002 */
2003 isl_bool FN(PW,plain_is_equal)(__isl_keep PW *pw1, __isl_keep PW *pw2)
2004 {
2005 int i;
2006 isl_bool equal, has_nan;
2007
2008 if (!pw1 || !pw2)
2009 return isl_bool_error;
2010
2011 has_nan = FN(PW,involves_nan)(pw1);
2012 if (has_nan >= 0 && !has_nan)
2013 has_nan = FN(PW,involves_nan)(pw2);
2014 if (has_nan < 0 || has_nan)
2015 return isl_bool_not(has_nan);
2016
2017 if (pw1 == pw2)
2018 return isl_bool_true;
2019 equal = FN(PW,has_equal_space)(pw1, pw2);
2020 if (equal < 0 || !equal)
2021 return equal;
2022
2023 pw1 = FN(PW,copy)(pw1);
2024 pw2 = FN(PW,copy)(pw2);
2025 pw1 = FN(PW,normalize)(pw1);
2026 pw2 = FN(PW,normalize)(pw2);
2027 if (!pw1 || !pw2)
2028 goto error;
2029
2030 equal = isl_bool_ok(pw1->n == pw2->n);
2031 for (i = 0; equal && i < pw1->n; ++i) {
2032 equal = isl_set_plain_is_equal(pw1->p[i].set, pw2->p[i].set);
2033 if (equal < 0)
2034 goto error;
2035 if (!equal)
2036 break;
2037 equal = FN(EL,plain_is_equal)(pw1->p[i].FIELD, pw2->p[i].FIELD);
2038 if (equal < 0)
2039 goto error;
2040 }
2041
2042 FN(PW,free)(pw1);
2043 FN(PW,free)(pw2);
2044 return equal;
2045 error:
2046 FN(PW,free)(pw1);
2047 FN(PW,free)(pw2);
2048 return isl_bool_error;
2049 }
2050
2051 /* Does "pw" involve any NaNs?
2052 */
2053 isl_bool FN(PW,involves_nan)(__isl_keep PW *pw)
2054 {
2055 int i;
2056
2057 if (!pw)
2058 return isl_bool_error;
2059 if (pw->n == 0)
2060 return isl_bool_false;
2061
2062 for (i = 0; i < pw->n; ++i) {
2063 isl_bool has_nan = FN(EL,involves_nan)(pw->p[i].FIELD);
2064 if (has_nan < 0 || has_nan)
2065 return has_nan;
2066 }
2067
2068 return isl_bool_false;
2069 }
Integer set library