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