?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_union_map_extract_map: ignore parameters when looking up entry
[isl.git] / isl_pw_templ.c
blob9521b11982034edfa3704b7e5ef2f0d87be572ab
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_aligned)(__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 if (!pw || !set)
788 goto error;
789
790 if (pw->n == 0) {
791 isl_set_free(set);
792 return pw;
793 }
794
795 pw = FN(PW,cow)(pw);
796 if (!pw)
797 goto error;
798
799 for (i = pw->n - 1; i >= 0; --i) {
800 pw->p[i].set = fn(pw->p[i].set, isl_set_copy(set));
801 if (FN(PW,exploit_equalities_and_remove_if_empty)(pw, i) < 0)
802 goto error;
803 }
804
805 isl_set_free(set);
806 return pw;
807 error:
808 isl_set_free(set);
809 FN(PW,free)(pw);
810 return NULL;
811 }
812
813 __isl_give PW *FN(PW,intersect_domain)(__isl_take PW *pw,
814 __isl_take isl_set *context)
815 {
816 FN(PW,align_params_set)(&pw, &context);
817 return FN(PW,restrict_domain_aligned)(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 FN(PW,align_params_set)(&pw, &context);
826 return FN(PW,restrict_domain_aligned)(pw, context,
827 &isl_set_intersect_params);
828 }
829
830 /* Given a piecewise expression "pw" with domain in a space [A -> B] and
831 * a set in the space A, intersect the domain with the set.
832 */
833 __isl_give PW *FN(PW,intersect_domain_wrapped_domain)(__isl_take PW *pw,
834 __isl_take isl_set *set)
835 {
836 FN(PW,align_params_set)(&pw, &set);
837 return FN(PW,restrict_domain_aligned)(pw, set,
838 &isl_set_intersect_factor_domain);
839 }
840
841 /* Given a piecewise expression "pw" with domain in a space [A -> B] and
842 * a set in the space B, intersect the domain with the set.
843 */
844 __isl_give PW *FN(PW,intersect_domain_wrapped_range)(__isl_take PW *pw,
845 __isl_take isl_set *set)
846 {
847 FN(PW,align_params_set)(&pw, &set);
848 return FN(PW,restrict_domain_aligned)(pw, set,
849 &isl_set_intersect_factor_range);
850 }
851
852 /* Subtract "domain' from the domain of "pw".
853 */
854 __isl_give PW *FN(PW,subtract_domain)(__isl_take PW *pw,
855 __isl_take isl_set *domain)
856 {
857 FN(PW,align_params_set)(&pw, &domain);
858 return FN(PW,restrict_domain_aligned)(pw, domain, &isl_set_subtract);
859 }
860
861 /* Compute the gist of "pw" with respect to the domain constraints
862 * of "context" for the case where the domain of the last element
863 * of "pw" is equal to "context".
864 * Call "fn_el" to compute the gist of this element, replace
865 * its domain by the universe and drop all other elements
866 * as their domains are necessarily disjoint from "context".
867 */
868 static __isl_give PW *FN(PW,gist_last)(__isl_take PW *pw,
869 __isl_take isl_set *context,
870 __isl_give EL *(*fn_el)(__isl_take EL *el, __isl_take isl_set *set))
871 {
872 int i;
873 isl_space *space;
874
875 for (i = 0; i < pw->n - 1; ++i) {
876 isl_set_free(pw->p[i].set);
877 FN(EL,free)(pw->p[i].FIELD);
878 }
879 pw->p[0].FIELD = pw->p[pw->n - 1].FIELD;
880 pw->p[0].set = pw->p[pw->n - 1].set;
881 pw->n = 1;
882
883 space = isl_set_get_space(context);
884 pw->p[0].FIELD = fn_el(pw->p[0].FIELD, context);
885 context = isl_set_universe(space);
886 isl_set_free(pw->p[0].set);
887 pw->p[0].set = context;
888
889 if (!pw->p[0].FIELD || !pw->p[0].set)
890 return FN(PW,free)(pw);
891
892 return pw;
893 }
894
895 /* Compute the gist of "pw" with respect to the domain constraints
896 * of "context". Call "fn_el" to compute the gist of the elements
897 * and "fn_dom" to compute the gist of the domains.
898 *
899 * If the piecewise expression is empty or the context is the universe,
900 * then nothing can be simplified.
901 */
902 static __isl_give PW *FN(PW,gist_aligned)(__isl_take PW *pw,
903 __isl_take isl_set *context,
904 __isl_give EL *(*fn_el)(__isl_take EL *el,
905 __isl_take isl_set *set),
906 __isl_give isl_set *(*fn_dom)(__isl_take isl_set *set,
907 __isl_take isl_basic_set *bset))
908 {
909 int i;
910 int is_universe;
911 isl_bool aligned;
912 isl_basic_set *hull = NULL;
913
914 if (!pw || !context)
915 goto error;
916
917 if (pw->n == 0) {
918 isl_set_free(context);
919 return pw;
920 }
921
922 is_universe = isl_set_plain_is_universe(context);
923 if (is_universe < 0)
924 goto error;
925 if (is_universe) {
926 isl_set_free(context);
927 return pw;
928 }
929
930 aligned = isl_set_space_has_equal_params(context, pw->dim);
931 if (aligned < 0)
932 goto error;
933 if (!aligned) {
934 pw = FN(PW,align_params)(pw, isl_set_get_space(context));
935 context = isl_set_align_params(context, FN(PW,get_space)(pw));
936 }
937
938 pw = FN(PW,cow)(pw);
939 if (!pw)
940 goto error;
941
942 if (pw->n == 1) {
943 int equal;
944
945 equal = isl_set_plain_is_equal(pw->p[0].set, context);
946 if (equal < 0)
947 goto error;
948 if (equal)
949 return FN(PW,gist_last)(pw, context, fn_el);
950 }
951
952 context = isl_set_compute_divs(context);
953 hull = isl_set_simple_hull(isl_set_copy(context));
954
955 for (i = pw->n - 1; i >= 0; --i) {
956 isl_set *set_i;
957 int empty;
958
959 if (i == pw->n - 1) {
960 int equal;
961 equal = isl_set_plain_is_equal(pw->p[i].set, context);
962 if (equal < 0)
963 goto error;
964 if (equal) {
965 isl_basic_set_free(hull);
966 return FN(PW,gist_last)(pw, context, fn_el);
967 }
968 }
969 set_i = isl_set_intersect(isl_set_copy(pw->p[i].set),
970 isl_set_copy(context));
971 empty = isl_set_plain_is_empty(set_i);
972 pw->p[i].FIELD = fn_el(pw->p[i].FIELD, set_i);
973 pw->p[i].set = fn_dom(pw->p[i].set, isl_basic_set_copy(hull));
974 if (empty < 0 || !pw->p[i].FIELD || !pw->p[i].set)
975 goto error;
976 if (empty) {
977 isl_set_free(pw->p[i].set);
978 FN(EL,free)(pw->p[i].FIELD);
979 if (i != pw->n - 1)
980 pw->p[i] = pw->p[pw->n - 1];
981 pw->n--;
982 }
983 }
984
985 isl_basic_set_free(hull);
986 isl_set_free(context);
987
988 return pw;
989 error:
990 FN(PW,free)(pw);
991 isl_basic_set_free(hull);
992 isl_set_free(context);
993 return NULL;
994 }
995
996 __isl_give PW *FN(PW,gist)(__isl_take PW *pw, __isl_take isl_set *context)
997 {
998 FN(PW,align_params_set)(&pw, &context);
999 return FN(PW,gist_aligned)(pw, context, &FN(EL,gist),
1000 &isl_set_gist_basic_set);
1001 }
1002
1003 __isl_give PW *FN(PW,gist_params)(__isl_take PW *pw,
1004 __isl_take isl_set *context)
1005 {
1006 FN(PW,align_params_set)(&pw, &context);
1007 return FN(PW,gist_aligned)(pw, context, &FN(EL,gist_params),
1008 &isl_set_gist_params_basic_set);
1009 }
1010
1011 /* Return -1 if the piece "p1" should be sorted before "p2"
1012 * and 1 if it should be sorted after "p2".
1013 * Return 0 if they do not need to be sorted in a specific order.
1014 *
1015 * The two pieces are compared on the basis of their function value expressions.
1016 */
1017 static int FN(PW,sort_field_cmp)(const void *p1, const void *p2, void *arg)
1018 {
1019 struct FN(PW,piece) const *pc1 = p1;
1020 struct FN(PW,piece) const *pc2 = p2;
1021
1022 return FN(EL,plain_cmp)(pc1->FIELD, pc2->FIELD);
1023 }
1024
1025 /* Sort the pieces of "pw" according to their function value
1026 * expressions and then combine pairs of adjacent pieces with
1027 * the same such expression.
1028 *
1029 * The sorting is performed in place because it does not
1030 * change the meaning of "pw", but care needs to be
1031 * taken not to change any possible other copies of "pw"
1032 * in case anything goes wrong.
1033 */
1034 __isl_give PW *FN(PW,sort)(__isl_take PW *pw)
1035 {
1036 int i, j;
1037 isl_set *set;
1038
1039 if (!pw)
1040 return NULL;
1041 if (pw->n <= 1)
1042 return pw;
1043 if (isl_sort(pw->p, pw->n, sizeof(pw->p[0]),
1044 &FN(PW,sort_field_cmp), NULL) < 0)
1045 return FN(PW,free)(pw);
1046 for (i = pw->n - 1; i >= 1; --i) {
1047 if (!FN(EL,plain_is_equal)(pw->p[i - 1].FIELD, pw->p[i].FIELD))
1048 continue;
1049 set = isl_set_union(isl_set_copy(pw->p[i - 1].set),
1050 isl_set_copy(pw->p[i].set));
1051 if (!set)
1052 return FN(PW,free)(pw);
1053 isl_set_free(pw->p[i].set);
1054 FN(EL,free)(pw->p[i].FIELD);
1055 isl_set_free(pw->p[i - 1].set);
1056 pw->p[i - 1].set = set;
1057 for (j = i + 1; j < pw->n; ++j)
1058 pw->p[j - 1] = pw->p[j];
1059 pw->n--;
1060 }
1061
1062 return pw;
1063 }
1064
1065 /* Coalesce the domains of "pw".
1066 *
1067 * Prior to the actual coalescing, first sort the pieces such that
1068 * pieces with the same function value expression are combined
1069 * into a single piece, the combined domain of which can then
1070 * be coalesced.
1071 */
1072 __isl_give PW *FN(PW,coalesce)(__isl_take PW *pw)
1073 {
1074 int i;
1075
1076 pw = FN(PW,sort)(pw);
1077 if (!pw)
1078 return NULL;
1079
1080 for (i = 0; i < pw->n; ++i) {
1081 pw->p[i].set = isl_set_coalesce(pw->p[i].set);
1082 if (!pw->p[i].set)
1083 goto error;
1084 }
1085
1086 return pw;
1087 error:
1088 FN(PW,free)(pw);
1089 return NULL;
1090 }
1091
1092 isl_ctx *FN(PW,get_ctx)(__isl_keep PW *pw)
1093 {
1094 return pw ? isl_space_get_ctx(pw->dim) : NULL;
1095 }
1096
1097 isl_bool FN(PW,involves_dims)(__isl_keep PW *pw, enum isl_dim_type type,
1098 unsigned first, unsigned n)
1099 {
1100 int i;
1101 enum isl_dim_type set_type;
1102
1103 if (!pw)
1104 return isl_bool_error;
1105 if (pw->n == 0 || n == 0)
1106 return isl_bool_false;
1107
1108 set_type = type == isl_dim_in ? isl_dim_set : type;
1109
1110 for (i = 0; i < pw->n; ++i) {
1111 isl_bool involves = FN(EL,involves_dims)(pw->p[i].FIELD,
1112 type, first, n);
1113 if (involves < 0 || involves)
1114 return involves;
1115 involves = isl_set_involves_dims(pw->p[i].set,
1116 set_type, first, n);
1117 if (involves < 0 || involves)
1118 return involves;
1119 }
1120 return isl_bool_false;
1121 }
1122
1123 __isl_give PW *FN(PW,set_dim_name)(__isl_take PW *pw,
1124 enum isl_dim_type type, unsigned pos, const char *s)
1125 {
1126 int i;
1127 enum isl_dim_type set_type;
1128
1129 pw = FN(PW,cow)(pw);
1130 if (!pw)
1131 return NULL;
1132
1133 set_type = type == isl_dim_in ? isl_dim_set : type;
1134
1135 pw->dim = isl_space_set_dim_name(pw->dim, type, pos, s);
1136 if (!pw->dim)
1137 goto error;
1138
1139 for (i = 0; i < pw->n; ++i) {
1140 pw->p[i].set = isl_set_set_dim_name(pw->p[i].set,
1141 set_type, pos, s);
1142 if (!pw->p[i].set)
1143 goto error;
1144 pw->p[i].FIELD = FN(EL,set_dim_name)(pw->p[i].FIELD, type, pos, s);
1145 if (!pw->p[i].FIELD)
1146 goto error;
1147 }
1148
1149 return pw;
1150 error:
1151 FN(PW,free)(pw);
1152 return NULL;
1153 }
1154
1155 __isl_give PW *FN(PW,drop_dims)(__isl_take PW *pw,
1156 enum isl_dim_type type, unsigned first, unsigned n)
1157 {
1158 int i;
1159 enum isl_dim_type set_type;
1160
1161 if (!pw)
1162 return NULL;
1163 if (n == 0 && !isl_space_get_tuple_name(pw->dim, type))
1164 return pw;
1165
1166 set_type = type == isl_dim_in ? isl_dim_set : type;
1167
1168 pw = FN(PW,cow)(pw);
1169 if (!pw)
1170 return NULL;
1171 pw->dim = isl_space_drop_dims(pw->dim, type, first, n);
1172 if (!pw->dim)
1173 goto error;
1174 for (i = 0; i < pw->n; ++i) {
1175 pw->p[i].FIELD = FN(EL,drop_dims)(pw->p[i].FIELD, type, first, n);
1176 if (!pw->p[i].FIELD)
1177 goto error;
1178 if (type == isl_dim_out)
1179 continue;
1180 pw->p[i].set = isl_set_drop(pw->p[i].set, set_type, first, n);
1181 if (!pw->p[i].set)
1182 goto error;
1183 }
1184
1185 return pw;
1186 error:
1187 FN(PW,free)(pw);
1188 return NULL;
1189 }
1190
1191 /* This function is very similar to drop_dims.
1192 * The only difference is that the cells may still involve
1193 * the specified dimensions. They are removed using
1194 * isl_set_project_out instead of isl_set_drop.
1195 */
1196 __isl_give PW *FN(PW,project_out)(__isl_take PW *pw,
1197 enum isl_dim_type type, unsigned first, unsigned n)
1198 {
1199 int i;
1200 enum isl_dim_type set_type;
1201
1202 if (!pw)
1203 return NULL;
1204 if (n == 0 && !isl_space_get_tuple_name(pw->dim, type))
1205 return pw;
1206
1207 set_type = type == isl_dim_in ? isl_dim_set : type;
1208
1209 pw = FN(PW,cow)(pw);
1210 if (!pw)
1211 return NULL;
1212 pw->dim = isl_space_drop_dims(pw->dim, type, first, n);
1213 if (!pw->dim)
1214 goto error;
1215 for (i = 0; i < pw->n; ++i) {
1216 pw->p[i].set = isl_set_project_out(pw->p[i].set,
1217 set_type, first, n);
1218 if (!pw->p[i].set)
1219 goto error;
1220 pw->p[i].FIELD = FN(EL,drop_dims)(pw->p[i].FIELD, type, first, n);
1221 if (!pw->p[i].FIELD)
1222 goto error;
1223 }
1224
1225 return pw;
1226 error:
1227 FN(PW,free)(pw);
1228 return NULL;
1229 }
1230
1231 /* Project the domain of pw onto its parameter space.
1232 */
1233 __isl_give PW *FN(PW,project_domain_on_params)(__isl_take PW *pw)
1234 {
1235 isl_space *space;
1236 isl_size n;
1237
1238 n = FN(PW,dim)(pw, isl_dim_in);
1239 if (n < 0)
1240 return FN(PW,free)(pw);
1241 pw = FN(PW,project_out)(pw, isl_dim_in, 0, n);
1242 space = FN(PW,get_domain_space)(pw);
1243 space = isl_space_params(space);
1244 pw = FN(PW,reset_domain_space)(pw, space);
1245 return pw;
1246 }
1247
1248 /* Drop all parameters not referenced by "pw".
1249 */
1250 __isl_give PW *FN(PW,drop_unused_params)(__isl_take PW *pw)
1251 {
1252 isl_size n;
1253 int i;
1254
1255 if (FN(PW,check_named_params)(pw) < 0)
1256 return FN(PW,free)(pw);
1257
1258 n = FN(PW,dim)(pw, isl_dim_param);
1259 if (n < 0)
1260 return FN(PW,free)(pw);
1261 for (i = n - 1; i >= 0; i--) {
1262 isl_bool involves;
1263
1264 involves = FN(PW,involves_dims)(pw, isl_dim_param, i, 1);
1265 if (involves < 0)
1266 return FN(PW,free)(pw);
1267 if (!involves)
1268 pw = FN(PW,drop_dims)(pw, isl_dim_param, i, 1);
1269 }
1270
1271 return pw;
1272 }
1273
1274 __isl_give PW *FN(PW,fix_dim)(__isl_take PW *pw,
1275 enum isl_dim_type type, unsigned pos, isl_int v)
1276 {
1277 int i;
1278
1279 if (!pw)
1280 return NULL;
1281
1282 if (type == isl_dim_in)
1283 type = isl_dim_set;
1284
1285 pw = FN(PW,cow)(pw);
1286 if (!pw)
1287 return NULL;
1288 for (i = 0; i < pw->n; ++i) {
1289 pw->p[i].set = isl_set_fix(pw->p[i].set, type, pos, v);
1290 if (FN(PW,exploit_equalities_and_remove_if_empty)(pw, i) < 0)
1291 return FN(PW,free)(pw);
1292 }
1293
1294 return pw;
1295 }
1296
1297 /* Fix the value of the variable at position "pos" of type "type" of "pw"
1298 * to be equal to "v".
1299 */
1300 __isl_give PW *FN(PW,fix_val)(__isl_take PW *pw,
1301 enum isl_dim_type type, unsigned pos, __isl_take isl_val *v)
1302 {
1303 if (!v)
1304 return FN(PW,free)(pw);
1305 if (!isl_val_is_int(v))
1306 isl_die(FN(PW,get_ctx)(pw), isl_error_invalid,
1307 "expecting integer value", goto error);
1308
1309 pw = FN(PW,fix_dim)(pw, type, pos, v->n);
1310 isl_val_free(v);
1311
1312 return pw;
1313 error:
1314 isl_val_free(v);
1315 return FN(PW,free)(pw);
1316 }
1317
1318 isl_size FN(PW,dim)(__isl_keep PW *pw, enum isl_dim_type type)
1319 {
1320 return isl_space_dim(FN(PW,peek_space)(pw), type);
1321 }
1322
1323 __isl_give PW *FN(PW,split_dims)(__isl_take PW *pw,
1324 enum isl_dim_type type, unsigned first, unsigned n)
1325 {
1326 int i;
1327
1328 if (!pw)
1329 return NULL;
1330 if (n == 0)
1331 return pw;
1332
1333 if (type == isl_dim_in)
1334 type = isl_dim_set;
1335
1336 pw = FN(PW,cow)(pw);
1337 if (!pw)
1338 return NULL;
1339 if (!pw->dim)
1340 goto error;
1341 for (i = 0; i < pw->n; ++i) {
1342 pw->p[i].set = isl_set_split_dims(pw->p[i].set, type, first, n);
1343 if (!pw->p[i].set)
1344 goto error;
1345 }
1346
1347 return pw;
1348 error:
1349 FN(PW,free)(pw);
1350 return NULL;
1351 }
1352
1353 /* Return the space of "pw".
1354 */
1355 __isl_keep isl_space *FN(PW,peek_space)(__isl_keep PW *pw)
1356 {
1357 return pw ? pw->dim : NULL;
1358 }
1359
1360 __isl_give isl_space *FN(PW,get_space)(__isl_keep PW *pw)
1361 {
1362 return isl_space_copy(FN(PW,peek_space)(pw));
1363 }
1364
1365 /* Return the space of "pw".
1366 * This may be either a copy or the space itself
1367 * if there is only one reference to "pw".
1368 * This allows the space to be modified inplace
1369 * if both the piecewise expression and its space have only a single reference.
1370 * The caller is not allowed to modify "pw" between this call and
1371 * a subsequent call to isl_pw_*_restore_*.
1372 * The only exception is that isl_pw_*_free can be called instead.
1373 */
1374 __isl_give isl_space *FN(PW,take_space)(__isl_keep PW *pw)
1375 {
1376 isl_space *space;
1377
1378 if (!pw)
1379 return NULL;
1380 if (pw->ref != 1)
1381 return FN(PW,get_space)(pw);
1382 space = pw->dim;
1383 pw->dim = NULL;
1384 return space;
1385 }
1386
1387 /* Set the space of "pw" to "space", where the space of "pw" may be missing
1388 * due to a preceding call to isl_pw_*_take_space.
1389 * However, in this case, "pw" only has a single reference and
1390 * then the call to isl_pw_*_cow has no effect.
1391 */
1392 __isl_give PW *FN(PW,restore_space)(__isl_take PW *pw,
1393 __isl_take isl_space *space)
1394 {
1395 if (!pw || !space)
1396 goto error;
1397
1398 if (pw->dim == space) {
1399 isl_space_free(space);
1400 return pw;
1401 }
1402
1403 pw = FN(PW,cow)(pw);
1404 if (!pw)
1405 goto error;
1406 isl_space_free(pw->dim);
1407 pw->dim = space;
1408
1409 return pw;
1410 error:
1411 FN(PW,free)(pw);
1412 isl_space_free(space);
1413 return NULL;
1414 }
1415
1416 /* Check that "pos" is a valid position for a cell in "pw".
1417 */
1418 static isl_stat FN(PW,check_pos)(__isl_keep PW *pw, int pos)
1419 {
1420 if (!pw)
1421 return isl_stat_error;
1422 if (pos < 0 || pos >= pw->n)
1423 isl_die(FN(PW,get_ctx)(pw), isl_error_internal,
1424 "position out of bounds", return isl_stat_error);
1425 return isl_stat_ok;
1426 }
1427
1428 /* Return the cell at position "pos" in "pw".
1429 */
1430 static __isl_keep isl_set *FN(PW,peek_domain_at)(__isl_keep PW *pw, int pos)
1431 {
1432 if (FN(PW,check_pos)(pw, pos) < 0)
1433 return NULL;
1434 return pw->p[pos].set;
1435 }
1436
1437 /* Return a copy of the base expression associated to
1438 * the cell at position "pos" in "pw".
1439 */
1440 __isl_give EL *FN(PW,get_base_at)(__isl_keep PW *pw, int pos)
1441 {
1442 if (FN(PW,check_pos)(pw, pos) < 0)
1443 return NULL;
1444 return FN(EL,copy)(pw->p[pos].FIELD);
1445 }
1446
1447 /* Return the base expression associated to
1448 * the cell at position "pos" in "pw".
1449 * This may be either a copy or the base expression itself
1450 * if there is only one reference to "pw".
1451 * This allows the base expression to be modified inplace
1452 * if both the piecewise expression and this base expression
1453 * have only a single reference.
1454 * The caller is not allowed to modify "pw" between this call and
1455 * a subsequent call to isl_pw_*_restore_*.
1456 * The only exception is that isl_pw_*_free can be called instead.
1457 */
1458 __isl_give EL *FN(PW,take_base_at)(__isl_keep PW *pw, int pos)
1459 {
1460 EL *el;
1461
1462 if (!pw)
1463 return NULL;
1464 if (pw->ref != 1)
1465 return FN(PW,get_base_at)(pw, pos);
1466 if (FN(PW,check_pos)(pw, pos) < 0)
1467 return NULL;
1468 el = pw->p[pos].FIELD;
1469 pw->p[pos].FIELD = NULL;
1470 return el;
1471 }
1472
1473 /* Set the base expression associated to
1474 * the cell at position "pos" in "pw" to "el",
1475 * where this base expression may be missing
1476 * due to a preceding call to isl_pw_*_take_base_at.
1477 * However, in this case, "pw" only has a single reference and
1478 * then the call to isl_pw_*_cow has no effect.
1479 */
1480 __isl_give PW *FN(PW,restore_base_at)(__isl_take PW *pw, int pos,
1481 __isl_take EL *el)
1482 {
1483 if (FN(PW,check_pos)(pw, pos) < 0 || !el)
1484 goto error;
1485
1486 if (pw->p[pos].FIELD == el) {
1487 FN(EL,free)(el);
1488 return pw;
1489 }
1490
1491 pw = FN(PW,cow)(pw);
1492 if (!pw)
1493 goto error;
1494 FN(EL,free)(pw->p[pos].FIELD);
1495 pw->p[pos].FIELD = el;
1496
1497 return pw;
1498 error:
1499 FN(PW,free)(pw);
1500 FN(EL,free)(el);
1501 return NULL;
1502 }
1503
1504 __isl_give isl_space *FN(PW,get_domain_space)(__isl_keep PW *pw)
1505 {
1506 return pw ? isl_space_domain(isl_space_copy(pw->dim)) : NULL;
1507 }
1508
1509 /* Return the position of the dimension of the given type and name
1510 * in "pw".
1511 * Return -1 if no such dimension can be found.
1512 */
1513 int FN(PW,find_dim_by_name)(__isl_keep PW *pw,
1514 enum isl_dim_type type, const char *name)
1515 {
1516 if (!pw)
1517 return -1;
1518 return isl_space_find_dim_by_name(pw->dim, type, name);
1519 }
1520
1521 /* Return the position of the dimension of the given type and identifier
1522 * in "pw".
1523 * Return -1 if no such dimension can be found.
1524 */
1525 static int FN(PW,find_dim_by_id)(__isl_keep PW *pw,
1526 enum isl_dim_type type, __isl_keep isl_id *id)
1527 {
1528 isl_space *space;
1529
1530 space = FN(PW,peek_space)(pw);
1531 return isl_space_find_dim_by_id(space, type, id);
1532 }
1533
1534 /* Does the piecewise expression "pw" depend in any way
1535 * on the parameter with identifier "id"?
1536 */
1537 isl_bool FN(PW,involves_param_id)(__isl_keep PW *pw, __isl_keep isl_id *id)
1538 {
1539 int pos;
1540
1541 if (!pw || !id)
1542 return isl_bool_error;
1543 if (pw->n == 0)
1544 return isl_bool_false;
1545
1546 pos = FN(PW,find_dim_by_id)(pw, isl_dim_param, id);
1547 if (pos < 0)
1548 return isl_bool_false;
1549 return FN(PW,involves_dims)(pw, isl_dim_param, pos, 1);
1550 }
1551
1552 /* Reset the space of "pw". Since we don't know if the elements
1553 * represent the spaces themselves or their domains, we pass along
1554 * both when we call their reset_space_and_domain.
1555 */
1556 static __isl_give PW *FN(PW,reset_space_and_domain)(__isl_take PW *pw,
1557 __isl_take isl_space *space, __isl_take isl_space *domain)
1558 {
1559 int i;
1560
1561 pw = FN(PW,cow)(pw);
1562 if (!pw || !space || !domain)
1563 goto error;
1564
1565 for (i = 0; i < pw->n; ++i) {
1566 pw->p[i].set = isl_set_reset_space(pw->p[i].set,
1567 isl_space_copy(domain));
1568 if (!pw->p[i].set)
1569 goto error;
1570 pw->p[i].FIELD = FN(EL,reset_space_and_domain)(pw->p[i].FIELD,
1571 isl_space_copy(space), isl_space_copy(domain));
1572 if (!pw->p[i].FIELD)
1573 goto error;
1574 }
1575
1576 isl_space_free(domain);
1577
1578 isl_space_free(pw->dim);
1579 pw->dim = space;
1580
1581 return pw;
1582 error:
1583 isl_space_free(domain);
1584 isl_space_free(space);
1585 FN(PW,free)(pw);
1586 return NULL;
1587 }
1588
1589 __isl_give PW *FN(PW,reset_domain_space)(__isl_take PW *pw,
1590 __isl_take isl_space *domain)
1591 {
1592 isl_space *space;
1593
1594 space = isl_space_extend_domain_with_range(isl_space_copy(domain),
1595 FN(PW,get_space)(pw));
1596 return FN(PW,reset_space_and_domain)(pw, space, domain);
1597 }
1598
1599 __isl_give PW *FN(PW,reset_space)(__isl_take PW *pw,
1600 __isl_take isl_space *space)
1601 {
1602 isl_space *domain;
1603
1604 domain = isl_space_domain(isl_space_copy(space));
1605 return FN(PW,reset_space_and_domain)(pw, space, domain);
1606 }
1607
1608 __isl_give PW *FN(PW,set_tuple_id)(__isl_take PW *pw, enum isl_dim_type type,
1609 __isl_take isl_id *id)
1610 {
1611 isl_space *space;
1612
1613 pw = FN(PW,cow)(pw);
1614 if (!pw)
1615 goto error;
1616
1617 space = FN(PW,get_space)(pw);
1618 space = isl_space_set_tuple_id(space, type, id);
1619
1620 return FN(PW,reset_space)(pw, space);
1621 error:
1622 isl_id_free(id);
1623 return FN(PW,free)(pw);
1624 }
1625
1626 /* Drop the id on the specified tuple.
1627 */
1628 __isl_give PW *FN(PW,reset_tuple_id)(__isl_take PW *pw, enum isl_dim_type type)
1629 {
1630 isl_space *space;
1631
1632 if (!pw)
1633 return NULL;
1634 if (!FN(PW,has_tuple_id)(pw, type))
1635 return pw;
1636
1637 pw = FN(PW,cow)(pw);
1638 if (!pw)
1639 return NULL;
1640
1641 space = FN(PW,get_space)(pw);
1642 space = isl_space_reset_tuple_id(space, type);
1643
1644 return FN(PW,reset_space)(pw, space);
1645 }
1646
1647 __isl_give PW *FN(PW,set_dim_id)(__isl_take PW *pw,
1648 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
1649 {
1650 pw = FN(PW,cow)(pw);
1651 if (!pw)
1652 goto error;
1653 pw->dim = isl_space_set_dim_id(pw->dim, type, pos, id);
1654 return FN(PW,reset_space)(pw, isl_space_copy(pw->dim));
1655 error:
1656 isl_id_free(id);
1657 return FN(PW,free)(pw);
1658 }
1659
1660 /* Reset the user pointer on all identifiers of parameters and tuples
1661 * of the space of "pw".
1662 */
1663 __isl_give PW *FN(PW,reset_user)(__isl_take PW *pw)
1664 {
1665 isl_space *space;
1666
1667 space = FN(PW,get_space)(pw);
1668 space = isl_space_reset_user(space);
1669
1670 return FN(PW,reset_space)(pw, space);
1671 }
1672
1673 isl_size FN(PW,n_piece)(__isl_keep PW *pw)
1674 {
1675 return pw ? pw->n : isl_size_error;
1676 }
1677
1678 isl_stat FN(PW,foreach_piece)(__isl_keep PW *pw,
1679 isl_stat (*fn)(__isl_take isl_set *set, __isl_take EL *el, void *user),
1680 void *user)
1681 {
1682 int i;
1683
1684 if (!pw)
1685 return isl_stat_error;
1686
1687 for (i = 0; i < pw->n; ++i)
1688 if (fn(isl_set_copy(pw->p[i].set),
1689 FN(EL,copy)(pw->p[i].FIELD), user) < 0)
1690 return isl_stat_error;
1691
1692 return isl_stat_ok;
1693 }
1694
1695 /* Does "test" succeed on every cell of "pw"?
1696 */
1697 isl_bool FN(PW,every_piece)(__isl_keep PW *pw,
1698 isl_bool (*test)(__isl_keep isl_set *set,
1699 __isl_keep EL *el, void *user), void *user)
1700 {
1701 int i;
1702
1703 if (!pw)
1704 return isl_bool_error;
1705
1706 for (i = 0; i < pw->n; ++i) {
1707 isl_bool r;
1708
1709 r = test(pw->p[i].set, pw->p[i].FIELD, user);
1710 if (r < 0 || !r)
1711 return r;
1712 }
1713
1714 return isl_bool_true;
1715 }
1716
1717 /* Is "pw" defined over a single universe domain?
1718 *
1719 * If the default value of this piecewise type is zero,
1720 * then a "pw" with a zero number of cells is also accepted
1721 * as it represents the default zero value.
1722 */
1723 isl_bool FN(FN(PW,isa),BASE)(__isl_keep PW *pw)
1724 {
1725 isl_size n;
1726
1727 n = FN(PW,n_piece)(pw);
1728 if (n < 0)
1729 return isl_bool_error;
1730 if (DEFAULT_IS_ZERO && n == 0)
1731 return isl_bool_true;
1732 if (n != 1)
1733 return isl_bool_false;
1734 return isl_set_plain_is_universe(FN(PW,peek_domain_at)(pw, 0));
1735 }
1736
1737 /* Return a zero base expression in the same space (and of the same type)
1738 * as "pw".
1739 */
1740 static __isl_give EL *FN(EL,zero_like_type)(__isl_take PW *pw OPT_TYPE_PARAM)
1741 {
1742 isl_space *space;
1743
1744 space = FN(PW,get_space)(pw);
1745 FN(PW,free)(pw);
1746 return FN(EL,zero_in_space)(space OPT_TYPE_ARG(NO_LOC));
1747 }
1748
1749 #ifndef HAS_TYPE
1750 /* Return a zero base expression in the same space as "pw".
1751 */
1752 static __isl_give EL *FN(EL,zero_like)(__isl_take PW *pw)
1753 {
1754 return FN(EL,zero_like_type)(pw);
1755 }
1756 #else
1757 /* Return a zero base expression in the same space and of the same type
1758 * as "pw".
1759 *
1760 * Pass along the type as an explicit argument for uniform handling
1761 * in isl_*_zero_like_type.
1762 */
1763 static __isl_give EL *FN(EL,zero_like)(__isl_take PW *pw)
1764 {
1765 enum isl_fold type;
1766
1767 type = FN(PW,get_type)(pw);
1768 if (type < 0)
1769 goto error;
1770 return FN(EL,zero_like_type)(pw, type);
1771 error:
1772 FN(PW,free)(pw);
1773 return NULL;
1774 }
1775 #endif
1776
1777 /* Given that "pw" is defined over a single universe domain,
1778 * return the base expression associated to this domain.
1779 *
1780 * If the number of cells is zero, then "pw" is of a piecewise type
1781 * with a default zero value and effectively represents zero.
1782 * In this case, create a zero base expression in the same space
1783 * (and with the same type).
1784 * Otherwise, simply extract the associated base expression.
1785 */
1786 __isl_give EL *FN(FN(PW,as),BASE)(__isl_take PW *pw)
1787 {
1788 isl_bool is_total;
1789 isl_size n;
1790 EL *el;
1791
1792 is_total = FN(FN(PW,isa),BASE)(pw);
1793 if (is_total < 0)
1794 goto error;
1795 if (!is_total)
1796 isl_die(FN(PW,get_ctx)(pw), isl_error_invalid,
1797 "expecting single total function", goto error);
1798 n = FN(PW,n_piece)(pw);
1799 if (n < 0)
1800 goto error;
1801 if (n == 0)
1802 return FN(EL,zero_like)(pw);
1803 el = FN(PW,take_base_at)(pw, 0);
1804 FN(PW,free)(pw);
1805 return el;
1806 error:
1807 FN(PW,free)(pw);
1808 return NULL;
1809 }
1810
1811 #ifdef HAS_TYPE
1812 /* Negate the type of "pw".
1813 */
1814 static __isl_give PW *FN(PW,negate_type)(__isl_take PW *pw)
1815 {
1816 pw = FN(PW,cow)(pw);
1817 if (!pw)
1818 return NULL;
1819 pw->type = isl_fold_type_negate(pw->type);
1820 return pw;
1821 }
1822 #else
1823 /* Negate the type of "pw".
1824 * Since "pw" does not have a type, do nothing.
1825 */
1826 static __isl_give PW *FN(PW,negate_type)(__isl_take PW *pw)
1827 {
1828 return pw;
1829 }
1830 #endif
1831
1832 __isl_give PW *FN(PW,mul_isl_int)(__isl_take PW *pw, isl_int v)
1833 {
1834 int i;
1835
1836 if (isl_int_is_one(v))
1837 return pw;
1838 if (pw && DEFAULT_IS_ZERO && isl_int_is_zero(v)) {
1839 PW *zero;
1840 isl_space *space = FN(PW,get_space)(pw);
1841 zero = FN(PW,ZERO)(space OPT_TYPE_ARG(pw->));
1842 FN(PW,free)(pw);
1843 return zero;
1844 }
1845 pw = FN(PW,cow)(pw);
1846 if (isl_int_is_neg(v))
1847 pw = FN(PW,negate_type)(pw);
1848 if (!pw)
1849 return NULL;
1850 if (pw->n == 0)
1851 return pw;
1852
1853 for (i = 0; i < pw->n; ++i) {
1854 pw->p[i].FIELD = FN(EL,scale)(pw->p[i].FIELD, v);
1855 if (!pw->p[i].FIELD)
1856 goto error;
1857 }
1858
1859 return pw;
1860 error:
1861 FN(PW,free)(pw);
1862 return NULL;
1863 }
1864
1865 /* Multiply the pieces of "pw" by "v" and return the result.
1866 */
1867 __isl_give PW *FN(PW,scale_val)(__isl_take PW *pw, __isl_take isl_val *v)
1868 {
1869 int i;
1870
1871 if (!pw || !v)
1872 goto error;
1873
1874 if (isl_val_is_one(v)) {
1875 isl_val_free(v);
1876 return pw;
1877 }
1878 if (pw && DEFAULT_IS_ZERO && isl_val_is_zero(v)) {
1879 PW *zero;
1880 isl_space *space = FN(PW,get_space)(pw);
1881 zero = FN(PW,ZERO)(space OPT_TYPE_ARG(pw->));
1882 FN(PW,free)(pw);
1883 isl_val_free(v);
1884 return zero;
1885 }
1886 if (pw->n == 0) {
1887 isl_val_free(v);
1888 return pw;
1889 }
1890 pw = FN(PW,cow)(pw);
1891 if (isl_val_is_neg(v))
1892 pw = FN(PW,negate_type)(pw);
1893 if (!pw)
1894 goto error;
1895
1896 for (i = 0; i < pw->n; ++i) {
1897 pw->p[i].FIELD = FN(EL,scale_val)(pw->p[i].FIELD,
1898 isl_val_copy(v));
1899 if (!pw->p[i].FIELD)
1900 goto error;
1901 }
1902
1903 isl_val_free(v);
1904 return pw;
1905 error:
1906 isl_val_free(v);
1907 FN(PW,free)(pw);
1908 return NULL;
1909 }
1910
1911 /* Divide the pieces of "pw" by "v" and return the result.
1912 */
1913 __isl_give PW *FN(PW,scale_down_val)(__isl_take PW *pw, __isl_take isl_val *v)
1914 {
1915 int i;
1916
1917 if (!pw || !v)
1918 goto error;
1919
1920 if (isl_val_is_one(v)) {
1921 isl_val_free(v);
1922 return pw;
1923 }
1924
1925 if (!isl_val_is_rat(v))
1926 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1927 "expecting rational factor", goto error);
1928 if (isl_val_is_zero(v))
1929 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1930 "cannot scale down by zero", goto error);
1931
1932 if (pw->n == 0) {
1933 isl_val_free(v);
1934 return pw;
1935 }
1936 pw = FN(PW,cow)(pw);
1937 if (isl_val_is_neg(v))
1938 pw = FN(PW,negate_type)(pw);
1939 if (!pw)
1940 goto error;
1941
1942 for (i = 0; i < pw->n; ++i) {
1943 pw->p[i].FIELD = FN(EL,scale_down_val)(pw->p[i].FIELD,
1944 isl_val_copy(v));
1945 if (!pw->p[i].FIELD)
1946 goto error;
1947 }
1948
1949 isl_val_free(v);
1950 return pw;
1951 error:
1952 isl_val_free(v);
1953 FN(PW,free)(pw);
1954 return NULL;
1955 }
1956
1957 __isl_give PW *FN(PW,scale)(__isl_take PW *pw, isl_int v)
1958 {
1959 return FN(PW,mul_isl_int)(pw, v);
1960 }
1961
1962 /* Apply some normalization to "pw".
1963 * In particular, sort the pieces according to their function value
1964 * expressions, combining pairs of adjacent pieces with
1965 * the same such expression, and then normalize the domains of the pieces.
1966 *
1967 * We normalize in place, but if anything goes wrong we need
1968 * to return NULL, so we need to make sure we don't change the
1969 * meaning of any possible other copies of "pw".
1970 */
1971 __isl_give PW *FN(PW,normalize)(__isl_take PW *pw)
1972 {
1973 int i;
1974 isl_set *set;
1975
1976 pw = FN(PW,sort)(pw);
1977 if (!pw)
1978 return NULL;
1979 for (i = 0; i < pw->n; ++i) {
1980 set = isl_set_normalize(isl_set_copy(pw->p[i].set));
1981 if (!set)
1982 return FN(PW,free)(pw);
1983 isl_set_free(pw->p[i].set);
1984 pw->p[i].set = set;
1985 }
1986
1987 return pw;
1988 }
1989
1990 /* Is pw1 obviously equal to pw2?
1991 * That is, do they have obviously identical cells and obviously identical
1992 * elements on each cell?
1993 *
1994 * If "pw1" or "pw2" contain any NaNs, then they are considered
1995 * not to be the same. A NaN is not equal to anything, not even
1996 * to another NaN.
1997 */
1998 isl_bool FN(PW,plain_is_equal)(__isl_keep PW *pw1, __isl_keep PW *pw2)
1999 {
2000 int i;
2001 isl_bool equal, has_nan;
2002
2003 if (!pw1 || !pw2)
2004 return isl_bool_error;
2005
2006 has_nan = FN(PW,involves_nan)(pw1);
2007 if (has_nan >= 0 && !has_nan)
2008 has_nan = FN(PW,involves_nan)(pw2);
2009 if (has_nan < 0 || has_nan)
2010 return isl_bool_not(has_nan);
2011
2012 if (pw1 == pw2)
2013 return isl_bool_true;
2014 equal = FN(PW,has_equal_space)(pw1, pw2);
2015 if (equal < 0 || !equal)
2016 return equal;
2017
2018 pw1 = FN(PW,copy)(pw1);
2019 pw2 = FN(PW,copy)(pw2);
2020 pw1 = FN(PW,normalize)(pw1);
2021 pw2 = FN(PW,normalize)(pw2);
2022 if (!pw1 || !pw2)
2023 goto error;
2024
2025 equal = isl_bool_ok(pw1->n == pw2->n);
2026 for (i = 0; equal && i < pw1->n; ++i) {
2027 equal = isl_set_plain_is_equal(pw1->p[i].set, pw2->p[i].set);
2028 if (equal < 0)
2029 goto error;
2030 if (!equal)
2031 break;
2032 equal = FN(EL,plain_is_equal)(pw1->p[i].FIELD, pw2->p[i].FIELD);
2033 if (equal < 0)
2034 goto error;
2035 }
2036
2037 FN(PW,free)(pw1);
2038 FN(PW,free)(pw2);
2039 return equal;
2040 error:
2041 FN(PW,free)(pw1);
2042 FN(PW,free)(pw2);
2043 return isl_bool_error;
2044 }
2045
2046 /* Does "pw" involve any NaNs?
2047 */
2048 isl_bool FN(PW,involves_nan)(__isl_keep PW *pw)
2049 {
2050 int i;
2051
2052 if (!pw)
2053 return isl_bool_error;
2054 if (pw->n == 0)
2055 return isl_bool_false;
2056
2057 for (i = 0; i < pw->n; ++i) {
2058 isl_bool has_nan = FN(EL,involves_nan)(pw->p[i].FIELD);
2059 if (has_nan < 0 || has_nan)
2060 return has_nan;
2061 }
2062
2063 return isl_bool_false;
2064 }
Integer set library