?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_pw_templ.c: extract out isl_pw_morph_templ.c
[isl.git] / isl_pw_templ.c
blobde40a3c3f0f298e58f534f72dec60de0df034798
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 #ifndef NO_REALIGN
308 __isl_give PW *FN(PW,realign_domain)(__isl_take PW *pw,
309 __isl_take isl_reordering *exp)
310 {
311 int i;
312
313 pw = FN(PW,cow)(pw);
314 if (!pw || !exp)
315 goto error;
316
317 for (i = 0; i < pw->n; ++i) {
318 pw->p[i].set = isl_set_realign(pw->p[i].set,
319 isl_reordering_copy(exp));
320 if (!pw->p[i].set)
321 goto error;
322 pw->p[i].FIELD = FN(EL,realign_domain)(pw->p[i].FIELD,
323 isl_reordering_copy(exp));
324 if (!pw->p[i].FIELD)
325 goto error;
326 }
327
328 pw = FN(PW,reset_domain_space)(pw, isl_reordering_get_space(exp));
329
330 isl_reordering_free(exp);
331 return pw;
332 error:
333 isl_reordering_free(exp);
334 FN(PW,free)(pw);
335 return NULL;
336 }
337
338 /* Check that "pw" has only named parameters, reporting an error
339 * if it does not.
340 */
341 isl_stat FN(PW,check_named_params)(__isl_keep PW *pw)
342 {
343 return isl_space_check_named_params(FN(PW,peek_space)(pw));
344 }
345
346 /* Align the parameters of "pw" to those of "model".
347 */
348 __isl_give PW *FN(PW,align_params)(__isl_take PW *pw, __isl_take isl_space *model)
349 {
350 isl_ctx *ctx;
351 isl_bool equal_params;
352
353 if (!pw || !model)
354 goto error;
355
356 ctx = isl_space_get_ctx(model);
357 if (!isl_space_has_named_params(model))
358 isl_die(ctx, isl_error_invalid,
359 "model has unnamed parameters", goto error);
360 if (FN(PW,check_named_params)(pw) < 0)
361 goto error;
362 equal_params = isl_space_has_equal_params(pw->dim, model);
363 if (equal_params < 0)
364 goto error;
365 if (!equal_params) {
366 isl_reordering *exp;
367
368 exp = isl_parameter_alignment_reordering(pw->dim, model);
369 exp = isl_reordering_extend_space(exp,
370 FN(PW,get_domain_space)(pw));
371 pw = FN(PW,realign_domain)(pw, exp);
372 }
373
374 isl_space_free(model);
375 return pw;
376 error:
377 isl_space_free(model);
378 FN(PW,free)(pw);
379 return NULL;
380 }
381
382 static __isl_give PW *FN(PW,align_params_pw_pw_and)(__isl_take PW *pw1,
383 __isl_take PW *pw2,
384 __isl_give PW *(*fn)(__isl_take PW *pw1, __isl_take PW *pw2))
385 {
386 isl_bool equal_params;
387
388 if (!pw1 || !pw2)
389 goto error;
390 equal_params = isl_space_has_equal_params(pw1->dim, pw2->dim);
391 if (equal_params < 0)
392 goto error;
393 if (equal_params)
394 return fn(pw1, pw2);
395 if (FN(PW,check_named_params)(pw1) < 0 ||
396 FN(PW,check_named_params)(pw2) < 0)
397 goto error;
398 pw1 = FN(PW,align_params)(pw1, FN(PW,get_space)(pw2));
399 pw2 = FN(PW,align_params)(pw2, FN(PW,get_space)(pw1));
400 return fn(pw1, pw2);
401 error:
402 FN(PW,free)(pw1);
403 FN(PW,free)(pw2);
404 return NULL;
405 }
406
407 static __isl_give PW *FN(PW,align_params_pw_set_and)(__isl_take PW *pw,
408 __isl_take isl_set *set,
409 __isl_give PW *(*fn)(__isl_take PW *pw, __isl_take isl_set *set))
410 {
411 isl_ctx *ctx;
412 isl_bool aligned;
413
414 if (!pw || !set)
415 goto error;
416 aligned = isl_set_space_has_equal_params(set, pw->dim);
417 if (aligned < 0)
418 goto error;
419 if (aligned)
420 return fn(pw, set);
421 ctx = FN(PW,get_ctx)(pw);
422 if (FN(PW,check_named_params)(pw) < 0)
423 goto error;
424 if (!isl_space_has_named_params(set->dim))
425 isl_die(ctx, isl_error_invalid,
426 "unaligned unnamed parameters", goto error);
427 pw = FN(PW,align_params)(pw, isl_set_get_space(set));
428 set = isl_set_align_params(set, FN(PW,get_space)(pw));
429 return fn(pw, set);
430 error:
431 FN(PW,free)(pw);
432 isl_set_free(set);
433 return NULL;
434 }
435 #endif
436
437 static __isl_give PW *FN(PW,union_add_aligned)(__isl_take PW *pw1,
438 __isl_take PW *pw2)
439 {
440 int i, j, n;
441 struct PW *res;
442 isl_ctx *ctx;
443 isl_set *set;
444
445 if (!pw1 || !pw2)
446 goto error;
447
448 ctx = isl_space_get_ctx(pw1->dim);
449 if (!OPT_EQUAL_TYPES(pw1->, pw2->))
450 isl_die(ctx, isl_error_invalid,
451 "fold types don't match", goto error);
452 isl_assert(ctx, isl_space_is_equal(pw1->dim, pw2->dim), goto error);
453
454 if (FN(PW,IS_ZERO)(pw1)) {
455 FN(PW,free)(pw1);
456 return pw2;
457 }
458
459 if (FN(PW,IS_ZERO)(pw2)) {
460 FN(PW,free)(pw2);
461 return pw1;
462 }
463
464 n = (pw1->n + 1) * (pw2->n + 1);
465 res = FN(PW,alloc_size)(isl_space_copy(pw1->dim)
466 OPT_TYPE_ARG(pw1->), n);
467
468 for (i = 0; i < pw1->n; ++i) {
469 set = isl_set_copy(pw1->p[i].set);
470 for (j = 0; j < pw2->n; ++j) {
471 struct isl_set *common;
472 EL *sum;
473 common = isl_set_intersect(isl_set_copy(pw1->p[i].set),
474 isl_set_copy(pw2->p[j].set));
475 if (isl_set_plain_is_empty(common)) {
476 isl_set_free(common);
477 continue;
478 }
479 set = isl_set_subtract(set,
480 isl_set_copy(pw2->p[j].set));
481
482 sum = FN(EL,add_on_domain)(common,
483 FN(EL,copy)(pw1->p[i].FIELD),
484 FN(EL,copy)(pw2->p[j].FIELD));
485
486 res = FN(PW,add_piece)(res, common, sum);
487 }
488 res = FN(PW,add_piece)(res, set, FN(EL,copy)(pw1->p[i].FIELD));
489 }
490
491 for (j = 0; j < pw2->n; ++j) {
492 set = isl_set_copy(pw2->p[j].set);
493 for (i = 0; i < pw1->n; ++i)
494 set = isl_set_subtract(set,
495 isl_set_copy(pw1->p[i].set));
496 res = FN(PW,add_piece)(res, set, FN(EL,copy)(pw2->p[j].FIELD));
497 }
498
499 FN(PW,free)(pw1);
500 FN(PW,free)(pw2);
501
502 return res;
503 error:
504 FN(PW,free)(pw1);
505 FN(PW,free)(pw2);
506 return NULL;
507 }
508
509 /* Private version of "union_add". For isl_pw_qpolynomial and
510 * isl_pw_qpolynomial_fold, we prefer to simply call it "add".
511 */
512 static __isl_give PW *FN(PW,union_add_)(__isl_take PW *pw1, __isl_take PW *pw2)
513 {
514 return FN(PW,align_params_pw_pw_and)(pw1, pw2,
515 &FN(PW,union_add_aligned));
516 }
517
518 /* Make sure "pw" has room for at least "n" more pieces.
519 *
520 * If there is only one reference to pw, we extend it in place.
521 * Otherwise, we create a new PW and copy the pieces.
522 */
523 static __isl_give PW *FN(PW,grow)(__isl_take PW *pw, int n)
524 {
525 int i;
526 isl_ctx *ctx;
527 PW *res;
528
529 if (!pw)
530 return NULL;
531 if (pw->n + n <= pw->size)
532 return pw;
533 ctx = FN(PW,get_ctx)(pw);
534 n += pw->n;
535 if (pw->ref == 1) {
536 res = isl_realloc(ctx, pw, struct PW,
537 sizeof(struct PW) + (n - 1) * sizeof(S(PW,piece)));
538 if (!res)
539 return FN(PW,free)(pw);
540 res->size = n;
541 return res;
542 }
543 res = FN(PW,alloc_size)(isl_space_copy(pw->dim) OPT_TYPE_ARG(pw->), n);
544 if (!res)
545 return FN(PW,free)(pw);
546 for (i = 0; i < pw->n; ++i)
547 res = FN(PW,add_piece)(res, isl_set_copy(pw->p[i].set),
548 FN(EL,copy)(pw->p[i].FIELD));
549 FN(PW,free)(pw);
550 return res;
551 }
552
553 static __isl_give PW *FN(PW,add_disjoint_aligned)(__isl_take PW *pw1,
554 __isl_take PW *pw2)
555 {
556 int i;
557 isl_ctx *ctx;
558
559 if (!pw1 || !pw2)
560 goto error;
561
562 if (pw1->size < pw1->n + pw2->n && pw1->n < pw2->n)
563 return FN(PW,add_disjoint_aligned)(pw2, pw1);
564
565 ctx = isl_space_get_ctx(pw1->dim);
566 if (!OPT_EQUAL_TYPES(pw1->, pw2->))
567 isl_die(ctx, isl_error_invalid,
568 "fold types don't match", goto error);
569 isl_assert(ctx, isl_space_is_equal(pw1->dim, pw2->dim), goto error);
570
571 if (FN(PW,IS_ZERO)(pw1)) {
572 FN(PW,free)(pw1);
573 return pw2;
574 }
575
576 if (FN(PW,IS_ZERO)(pw2)) {
577 FN(PW,free)(pw2);
578 return pw1;
579 }
580
581 pw1 = FN(PW,grow)(pw1, pw2->n);
582 if (!pw1)
583 goto error;
584
585 for (i = 0; i < pw2->n; ++i)
586 pw1 = FN(PW,add_piece)(pw1,
587 isl_set_copy(pw2->p[i].set),
588 FN(EL,copy)(pw2->p[i].FIELD));
589
590 FN(PW,free)(pw2);
591
592 return pw1;
593 error:
594 FN(PW,free)(pw1);
595 FN(PW,free)(pw2);
596 return NULL;
597 }
598
599 __isl_give PW *FN(PW,add_disjoint)(__isl_take PW *pw1, __isl_take PW *pw2)
600 {
601 return FN(PW,align_params_pw_pw_and)(pw1, pw2,
602 &FN(PW,add_disjoint_aligned));
603 }
604
605 /* This function is currently only used from isl_aff.c
606 */
607 static __isl_give PW *FN(PW,on_shared_domain_in)(__isl_take PW *pw1,
608 __isl_take PW *pw2, __isl_take isl_space *space,
609 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))
610 __attribute__ ((unused));
611
612 /* Apply "fn" to pairs of elements from pw1 and pw2 on shared domains.
613 * The result of "fn" (and therefore also of this function) lives in "space".
614 */
615 static __isl_give PW *FN(PW,on_shared_domain_in)(__isl_take PW *pw1,
616 __isl_take PW *pw2, __isl_take isl_space *space,
617 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))
618 {
619 int i, j, n;
620 PW *res = NULL;
621
622 if (!pw1 || !pw2)
623 goto error;
624
625 n = pw1->n * pw2->n;
626 res = FN(PW,alloc_size)(isl_space_copy(space) OPT_TYPE_ARG(pw1->), n);
627
628 for (i = 0; i < pw1->n; ++i) {
629 for (j = 0; j < pw2->n; ++j) {
630 isl_set *common;
631 EL *res_ij;
632 int empty;
633
634 common = isl_set_intersect(
635 isl_set_copy(pw1->p[i].set),
636 isl_set_copy(pw2->p[j].set));
637 empty = isl_set_plain_is_empty(common);
638 if (empty < 0 || empty) {
639 isl_set_free(common);
640 if (empty < 0)
641 goto error;
642 continue;
643 }
644
645 res_ij = fn(FN(EL,copy)(pw1->p[i].FIELD),
646 FN(EL,copy)(pw2->p[j].FIELD));
647 res_ij = FN(EL,gist)(res_ij, isl_set_copy(common));
648
649 res = FN(PW,add_piece)(res, common, res_ij);
650 }
651 }
652
653 isl_space_free(space);
654 FN(PW,free)(pw1);
655 FN(PW,free)(pw2);
656 return res;
657 error:
658 isl_space_free(space);
659 FN(PW,free)(pw1);
660 FN(PW,free)(pw2);
661 FN(PW,free)(res);
662 return NULL;
663 }
664
665 /* This function is currently only used from isl_aff.c
666 */
667 static __isl_give PW *FN(PW,on_shared_domain)(__isl_take PW *pw1,
668 __isl_take PW *pw2,
669 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))
670 __attribute__ ((unused));
671
672 /* Apply "fn" to pairs of elements from pw1 and pw2 on shared domains.
673 * The result of "fn" is assumed to live in the same space as "pw1" and "pw2".
674 */
675 static __isl_give PW *FN(PW,on_shared_domain)(__isl_take PW *pw1,
676 __isl_take PW *pw2,
677 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))
678 {
679 isl_space *space;
680
681 if (!pw1 || !pw2)
682 goto error;
683
684 space = isl_space_copy(pw1->dim);
685 return FN(PW,on_shared_domain_in)(pw1, pw2, space, fn);
686 error:
687 FN(PW,free)(pw1);
688 FN(PW,free)(pw2);
689 return NULL;
690 }
691
692 #ifndef NO_NEG
693 __isl_give PW *FN(PW,neg)(__isl_take PW *pw)
694 {
695 int i;
696
697 if (!pw)
698 return NULL;
699
700 if (FN(PW,IS_ZERO)(pw))
701 return pw;
702
703 pw = FN(PW,cow)(pw);
704 if (!pw)
705 return NULL;
706
707 for (i = 0; i < pw->n; ++i) {
708 pw->p[i].FIELD = FN(EL,neg)(pw->p[i].FIELD);
709 if (!pw->p[i].FIELD)
710 return FN(PW,free)(pw);
711 }
712
713 return pw;
714 }
715 #endif
716
717 #ifndef NO_SUB
718 __isl_give PW *FN(PW,sub)(__isl_take PW *pw1, __isl_take PW *pw2)
719 {
720 return FN(PW,add)(pw1, FN(PW,neg)(pw2));
721 }
722 #endif
723
724 /* Return the parameter domain of "pw".
725 */
726 __isl_give isl_set *FN(PW,params)(__isl_take PW *pw)
727 {
728 return isl_set_params(FN(PW,domain)(pw));
729 }
730
731 __isl_give isl_set *FN(PW,domain)(__isl_take PW *pw)
732 {
733 int i;
734 isl_set *dom;
735
736 if (!pw)
737 return NULL;
738
739 dom = isl_set_empty(FN(PW,get_domain_space)(pw));
740 for (i = 0; i < pw->n; ++i)
741 dom = isl_set_union_disjoint(dom, isl_set_copy(pw->p[i].set));
742
743 FN(PW,free)(pw);
744
745 return dom;
746 }
747
748 /* Exploit the equalities in the domain of piece "i" of "pw"
749 * to simplify the associated function.
750 * If the domain of piece "i" is empty, then remove it entirely,
751 * replacing it with the final piece.
752 */
753 static int FN(PW,exploit_equalities_and_remove_if_empty)(__isl_keep PW *pw,
754 int i)
755 {
756 isl_basic_set *aff;
757 int empty = isl_set_plain_is_empty(pw->p[i].set);
758
759 if (empty < 0)
760 return -1;
761 if (empty) {
762 isl_set_free(pw->p[i].set);
763 FN(EL,free)(pw->p[i].FIELD);
764 if (i != pw->n - 1)
765 pw->p[i] = pw->p[pw->n - 1];
766 pw->n--;
767
768 return 0;
769 }
770
771 aff = isl_set_affine_hull(isl_set_copy(pw->p[i].set));
772 pw->p[i].FIELD = FN(EL,substitute_equalities)(pw->p[i].FIELD, aff);
773 if (!pw->p[i].FIELD)
774 return -1;
775
776 return 0;
777 }
778
779 /* Convert a piecewise expression defined over a parameter domain
780 * into one that is defined over a zero-dimensional set.
781 */
782 __isl_give PW *FN(PW,from_range)(__isl_take PW *pw)
783 {
784 isl_space *space;
785
786 if (!pw)
787 return NULL;
788 if (!isl_space_is_set(pw->dim))
789 isl_die(FN(PW,get_ctx)(pw), isl_error_invalid,
790 "not living in a set space", return FN(PW,free)(pw));
791
792 space = FN(PW,get_space)(pw);
793 space = isl_space_from_range(space);
794 pw = FN(PW,reset_space)(pw, space);
795
796 return pw;
797 }
798
799 /* Fix the value of the given parameter or domain dimension of "pw"
800 * to be equal to "value".
801 */
802 __isl_give PW *FN(PW,fix_si)(__isl_take PW *pw, enum isl_dim_type type,
803 unsigned pos, int value)
804 {
805 int i;
806
807 if (!pw)
808 return NULL;
809
810 if (type == isl_dim_out)
811 isl_die(FN(PW,get_ctx)(pw), isl_error_invalid,
812 "cannot fix output dimension", return FN(PW,free)(pw));
813
814 if (pw->n == 0)
815 return pw;
816
817 if (type == isl_dim_in)
818 type = isl_dim_set;
819
820 pw = FN(PW,cow)(pw);
821 if (!pw)
822 return FN(PW,free)(pw);
823
824 for (i = pw->n - 1; i >= 0; --i) {
825 pw->p[i].set = isl_set_fix_si(pw->p[i].set, type, pos, value);
826 if (FN(PW,exploit_equalities_and_remove_if_empty)(pw, i) < 0)
827 return FN(PW,free)(pw);
828 }
829
830 return pw;
831 }
832
833 /* Restrict the domain of "pw" by combining each cell
834 * with "set" through a call to "fn", where "fn" may be
835 * isl_set_intersect, isl_set_intersect_params, isl_set_intersect_factor_domain,
836 * isl_set_intersect_factor_range or isl_set_subtract.
837 */
838 static __isl_give PW *FN(PW,restrict_domain_aligned)(__isl_take PW *pw,
839 __isl_take isl_set *set,
840 __isl_give isl_set *(*fn)(__isl_take isl_set *set1,
841 __isl_take isl_set *set2))
842 {
843 int i;
844
845 if (!pw || !set)
846 goto error;
847
848 if (pw->n == 0) {
849 isl_set_free(set);
850 return pw;
851 }
852
853 pw = FN(PW,cow)(pw);
854 if (!pw)
855 goto error;
856
857 for (i = pw->n - 1; i >= 0; --i) {
858 pw->p[i].set = fn(pw->p[i].set, isl_set_copy(set));
859 if (FN(PW,exploit_equalities_and_remove_if_empty)(pw, i) < 0)
860 goto error;
861 }
862
863 isl_set_free(set);
864 return pw;
865 error:
866 isl_set_free(set);
867 FN(PW,free)(pw);
868 return NULL;
869 }
870
871 static __isl_give PW *FN(PW,intersect_domain_aligned)(__isl_take PW *pw,
872 __isl_take isl_set *set)
873 {
874 return FN(PW,restrict_domain_aligned)(pw, set, &isl_set_intersect);
875 }
876
877 __isl_give PW *FN(PW,intersect_domain)(__isl_take PW *pw,
878 __isl_take isl_set *context)
879 {
880 return FN(PW,align_params_pw_set_and)(pw, context,
881 &FN(PW,intersect_domain_aligned));
882 }
883
884 static __isl_give PW *FN(PW,intersect_params_aligned)(__isl_take PW *pw,
885 __isl_take isl_set *set)
886 {
887 return FN(PW,restrict_domain_aligned)(pw, set,
888 &isl_set_intersect_params);
889 }
890
891 /* Intersect the domain of "pw" with the parameter domain "context".
892 */
893 __isl_give PW *FN(PW,intersect_params)(__isl_take PW *pw,
894 __isl_take isl_set *context)
895 {
896 return FN(PW,align_params_pw_set_and)(pw, context,
897 &FN(PW,intersect_params_aligned));
898 }
899
900 /* Given a piecewise expression "pw" with domain in a space [A -> B] and
901 * a set in the space A, intersect the domain with the set,
902 * assuming the parameters have been aligned.
903 */
904 static __isl_give PW *FN(PW,intersect_domain_wrapped_domain_aligned)(
905 __isl_take PW *pw, __isl_take isl_set *set)
906 {
907 return FN(PW,restrict_domain_aligned)(pw, set,
908 &isl_set_intersect_factor_domain);
909 }
910
911 /* Given a piecewise expression "pw" with domain in a space [A -> B] and
912 * a set in the space A, intersect the domain with the set.
913 */
914 __isl_give PW *FN(PW,intersect_domain_wrapped_domain)(__isl_take PW *pw,
915 __isl_take isl_set *set)
916 {
917 return FN(PW,align_params_pw_set_and)(pw, set,
918 &FN(PW,intersect_domain_wrapped_domain_aligned));
919 }
920
921 /* Given a piecewise expression "pw" with domain in a space [A -> B] and
922 * a set in the space B, intersect the domain with the set,
923 * assuming the parameters have been aligned.
924 */
925 static __isl_give PW *FN(PW,intersect_domain_wrapped_range_aligned)(
926 __isl_take PW *pw, __isl_take isl_set *set)
927 {
928 return FN(PW,restrict_domain_aligned)(pw, set,
929 &isl_set_intersect_factor_range);
930 }
931
932 /* Given a piecewise expression "pw" with domain in a space [A -> B] and
933 * a set in the space B, intersect the domain with the set.
934 */
935 __isl_give PW *FN(PW,intersect_domain_wrapped_range)(__isl_take PW *pw,
936 __isl_take isl_set *set)
937 {
938 return FN(PW,align_params_pw_set_and)(pw, set,
939 &FN(PW,intersect_domain_wrapped_range_aligned));
940 }
941
942 /* Subtract "domain' from the domain of "pw", assuming their
943 * parameters have been aligned.
944 */
945 static __isl_give PW *FN(PW,subtract_domain_aligned)(__isl_take PW *pw,
946 __isl_take isl_set *domain)
947 {
948 return FN(PW,restrict_domain_aligned)(pw, domain, &isl_set_subtract);
949 }
950
951 /* Subtract "domain' from the domain of "pw".
952 */
953 __isl_give PW *FN(PW,subtract_domain)(__isl_take PW *pw,
954 __isl_take isl_set *domain)
955 {
956 return FN(PW,align_params_pw_set_and)(pw, domain,
957 &FN(PW,subtract_domain_aligned));
958 }
959
960 /* Compute the gist of "pw" with respect to the domain constraints
961 * of "context" for the case where the domain of the last element
962 * of "pw" is equal to "context".
963 * Call "fn_el" to compute the gist of this element, replace
964 * its domain by the universe and drop all other elements
965 * as their domains are necessarily disjoint from "context".
966 */
967 static __isl_give PW *FN(PW,gist_last)(__isl_take PW *pw,
968 __isl_take isl_set *context,
969 __isl_give EL *(*fn_el)(__isl_take EL *el, __isl_take isl_set *set))
970 {
971 int i;
972 isl_space *space;
973
974 for (i = 0; i < pw->n - 1; ++i) {
975 isl_set_free(pw->p[i].set);
976 FN(EL,free)(pw->p[i].FIELD);
977 }
978 pw->p[0].FIELD = pw->p[pw->n - 1].FIELD;
979 pw->p[0].set = pw->p[pw->n - 1].set;
980 pw->n = 1;
981
982 space = isl_set_get_space(context);
983 pw->p[0].FIELD = fn_el(pw->p[0].FIELD, context);
984 context = isl_set_universe(space);
985 isl_set_free(pw->p[0].set);
986 pw->p[0].set = context;
987
988 if (!pw->p[0].FIELD || !pw->p[0].set)
989 return FN(PW,free)(pw);
990
991 return pw;
992 }
993
994 /* Compute the gist of "pw" with respect to the domain constraints
995 * of "context". Call "fn_el" to compute the gist of the elements
996 * and "fn_dom" to compute the gist of the domains.
997 *
998 * If the piecewise expression is empty or the context is the universe,
999 * then nothing can be simplified.
1000 */
1001 static __isl_give PW *FN(PW,gist_aligned)(__isl_take PW *pw,
1002 __isl_take isl_set *context,
1003 __isl_give EL *(*fn_el)(__isl_take EL *el,
1004 __isl_take isl_set *set),
1005 __isl_give isl_set *(*fn_dom)(__isl_take isl_set *set,
1006 __isl_take isl_basic_set *bset))
1007 {
1008 int i;
1009 int is_universe;
1010 isl_bool aligned;
1011 isl_basic_set *hull = NULL;
1012
1013 if (!pw || !context)
1014 goto error;
1015
1016 if (pw->n == 0) {
1017 isl_set_free(context);
1018 return pw;
1019 }
1020
1021 is_universe = isl_set_plain_is_universe(context);
1022 if (is_universe < 0)
1023 goto error;
1024 if (is_universe) {
1025 isl_set_free(context);
1026 return pw;
1027 }
1028
1029 aligned = isl_set_space_has_equal_params(context, pw->dim);
1030 if (aligned < 0)
1031 goto error;
1032 if (!aligned) {
1033 pw = FN(PW,align_params)(pw, isl_set_get_space(context));
1034 context = isl_set_align_params(context, FN(PW,get_space)(pw));
1035 }
1036
1037 pw = FN(PW,cow)(pw);
1038 if (!pw)
1039 goto error;
1040
1041 if (pw->n == 1) {
1042 int equal;
1043
1044 equal = isl_set_plain_is_equal(pw->p[0].set, context);
1045 if (equal < 0)
1046 goto error;
1047 if (equal)
1048 return FN(PW,gist_last)(pw, context, fn_el);
1049 }
1050
1051 context = isl_set_compute_divs(context);
1052 hull = isl_set_simple_hull(isl_set_copy(context));
1053
1054 for (i = pw->n - 1; i >= 0; --i) {
1055 isl_set *set_i;
1056 int empty;
1057
1058 if (i == pw->n - 1) {
1059 int equal;
1060 equal = isl_set_plain_is_equal(pw->p[i].set, context);
1061 if (equal < 0)
1062 goto error;
1063 if (equal) {
1064 isl_basic_set_free(hull);
1065 return FN(PW,gist_last)(pw, context, fn_el);
1066 }
1067 }
1068 set_i = isl_set_intersect(isl_set_copy(pw->p[i].set),
1069 isl_set_copy(context));
1070 empty = isl_set_plain_is_empty(set_i);
1071 pw->p[i].FIELD = fn_el(pw->p[i].FIELD, set_i);
1072 pw->p[i].set = fn_dom(pw->p[i].set, isl_basic_set_copy(hull));
1073 if (empty < 0 || !pw->p[i].FIELD || !pw->p[i].set)
1074 goto error;
1075 if (empty) {
1076 isl_set_free(pw->p[i].set);
1077 FN(EL,free)(pw->p[i].FIELD);
1078 if (i != pw->n - 1)
1079 pw->p[i] = pw->p[pw->n - 1];
1080 pw->n--;
1081 }
1082 }
1083
1084 isl_basic_set_free(hull);
1085 isl_set_free(context);
1086
1087 return pw;
1088 error:
1089 FN(PW,free)(pw);
1090 isl_basic_set_free(hull);
1091 isl_set_free(context);
1092 return NULL;
1093 }
1094
1095 static __isl_give PW *FN(PW,gist_domain_aligned)(__isl_take PW *pw,
1096 __isl_take isl_set *set)
1097 {
1098 return FN(PW,gist_aligned)(pw, set, &FN(EL,gist),
1099 &isl_set_gist_basic_set);
1100 }
1101
1102 __isl_give PW *FN(PW,gist)(__isl_take PW *pw, __isl_take isl_set *context)
1103 {
1104 return FN(PW,align_params_pw_set_and)(pw, context,
1105 &FN(PW,gist_domain_aligned));
1106 }
1107
1108 static __isl_give PW *FN(PW,gist_params_aligned)(__isl_take PW *pw,
1109 __isl_take isl_set *set)
1110 {
1111 return FN(PW,gist_aligned)(pw, set, &FN(EL,gist_params),
1112 &isl_set_gist_params_basic_set);
1113 }
1114
1115 __isl_give PW *FN(PW,gist_params)(__isl_take PW *pw,
1116 __isl_take isl_set *context)
1117 {
1118 return FN(PW,align_params_pw_set_and)(pw, context,
1119 &FN(PW,gist_params_aligned));
1120 }
1121
1122 /* Return -1 if the piece "p1" should be sorted before "p2"
1123 * and 1 if it should be sorted after "p2".
1124 * Return 0 if they do not need to be sorted in a specific order.
1125 *
1126 * The two pieces are compared on the basis of their function value expressions.
1127 */
1128 static int FN(PW,sort_field_cmp)(const void *p1, const void *p2, void *arg)
1129 {
1130 struct FN(PW,piece) const *pc1 = p1;
1131 struct FN(PW,piece) const *pc2 = p2;
1132
1133 return FN(EL,plain_cmp)(pc1->FIELD, pc2->FIELD);
1134 }
1135
1136 /* Sort the pieces of "pw" according to their function value
1137 * expressions and then combine pairs of adjacent pieces with
1138 * the same such expression.
1139 *
1140 * The sorting is performed in place because it does not
1141 * change the meaning of "pw", but care needs to be
1142 * taken not to change any possible other copies of "pw"
1143 * in case anything goes wrong.
1144 */
1145 __isl_give PW *FN(PW,sort)(__isl_take PW *pw)
1146 {
1147 int i, j;
1148 isl_set *set;
1149
1150 if (!pw)
1151 return NULL;
1152 if (pw->n <= 1)
1153 return pw;
1154 if (isl_sort(pw->p, pw->n, sizeof(pw->p[0]),
1155 &FN(PW,sort_field_cmp), NULL) < 0)
1156 return FN(PW,free)(pw);
1157 for (i = pw->n - 1; i >= 1; --i) {
1158 if (!FN(EL,plain_is_equal)(pw->p[i - 1].FIELD, pw->p[i].FIELD))
1159 continue;
1160 set = isl_set_union(isl_set_copy(pw->p[i - 1].set),
1161 isl_set_copy(pw->p[i].set));
1162 if (!set)
1163 return FN(PW,free)(pw);
1164 isl_set_free(pw->p[i].set);
1165 FN(EL,free)(pw->p[i].FIELD);
1166 isl_set_free(pw->p[i - 1].set);
1167 pw->p[i - 1].set = set;
1168 for (j = i + 1; j < pw->n; ++j)
1169 pw->p[j - 1] = pw->p[j];
1170 pw->n--;
1171 }
1172
1173 return pw;
1174 }
1175
1176 /* Coalesce the domains of "pw".
1177 *
1178 * Prior to the actual coalescing, first sort the pieces such that
1179 * pieces with the same function value expression are combined
1180 * into a single piece, the combined domain of which can then
1181 * be coalesced.
1182 */
1183 __isl_give PW *FN(PW,coalesce)(__isl_take PW *pw)
1184 {
1185 int i;
1186
1187 pw = FN(PW,sort)(pw);
1188 if (!pw)
1189 return NULL;
1190
1191 for (i = 0; i < pw->n; ++i) {
1192 pw->p[i].set = isl_set_coalesce(pw->p[i].set);
1193 if (!pw->p[i].set)
1194 goto error;
1195 }
1196
1197 return pw;
1198 error:
1199 FN(PW,free)(pw);
1200 return NULL;
1201 }
1202
1203 isl_ctx *FN(PW,get_ctx)(__isl_keep PW *pw)
1204 {
1205 return pw ? isl_space_get_ctx(pw->dim) : NULL;
1206 }
1207
1208 isl_bool FN(PW,involves_dims)(__isl_keep PW *pw, enum isl_dim_type type,
1209 unsigned first, unsigned n)
1210 {
1211 int i;
1212 enum isl_dim_type set_type;
1213
1214 if (!pw)
1215 return isl_bool_error;
1216 if (pw->n == 0 || n == 0)
1217 return isl_bool_false;
1218
1219 set_type = type == isl_dim_in ? isl_dim_set : type;
1220
1221 for (i = 0; i < pw->n; ++i) {
1222 isl_bool involves = FN(EL,involves_dims)(pw->p[i].FIELD,
1223 type, first, n);
1224 if (involves < 0 || involves)
1225 return involves;
1226 involves = isl_set_involves_dims(pw->p[i].set,
1227 set_type, first, n);
1228 if (involves < 0 || involves)
1229 return involves;
1230 }
1231 return isl_bool_false;
1232 }
1233
1234 __isl_give PW *FN(PW,set_dim_name)(__isl_take PW *pw,
1235 enum isl_dim_type type, unsigned pos, const char *s)
1236 {
1237 int i;
1238 enum isl_dim_type set_type;
1239
1240 pw = FN(PW,cow)(pw);
1241 if (!pw)
1242 return NULL;
1243
1244 set_type = type == isl_dim_in ? isl_dim_set : type;
1245
1246 pw->dim = isl_space_set_dim_name(pw->dim, type, pos, s);
1247 if (!pw->dim)
1248 goto error;
1249
1250 for (i = 0; i < pw->n; ++i) {
1251 pw->p[i].set = isl_set_set_dim_name(pw->p[i].set,
1252 set_type, pos, s);
1253 if (!pw->p[i].set)
1254 goto error;
1255 pw->p[i].FIELD = FN(EL,set_dim_name)(pw->p[i].FIELD, type, pos, s);
1256 if (!pw->p[i].FIELD)
1257 goto error;
1258 }
1259
1260 return pw;
1261 error:
1262 FN(PW,free)(pw);
1263 return NULL;
1264 }
1265
1266 __isl_give PW *FN(PW,drop_dims)(__isl_take PW *pw,
1267 enum isl_dim_type type, unsigned first, unsigned n)
1268 {
1269 int i;
1270 enum isl_dim_type set_type;
1271
1272 if (!pw)
1273 return NULL;
1274 if (n == 0 && !isl_space_get_tuple_name(pw->dim, type))
1275 return pw;
1276
1277 set_type = type == isl_dim_in ? isl_dim_set : type;
1278
1279 pw = FN(PW,cow)(pw);
1280 if (!pw)
1281 return NULL;
1282 pw->dim = isl_space_drop_dims(pw->dim, type, first, n);
1283 if (!pw->dim)
1284 goto error;
1285 for (i = 0; i < pw->n; ++i) {
1286 pw->p[i].FIELD = FN(EL,drop_dims)(pw->p[i].FIELD, type, first, n);
1287 if (!pw->p[i].FIELD)
1288 goto error;
1289 if (type == isl_dim_out)
1290 continue;
1291 pw->p[i].set = isl_set_drop(pw->p[i].set, set_type, first, n);
1292 if (!pw->p[i].set)
1293 goto error;
1294 }
1295
1296 return pw;
1297 error:
1298 FN(PW,free)(pw);
1299 return NULL;
1300 }
1301
1302 /* This function is very similar to drop_dims.
1303 * The only difference is that the cells may still involve
1304 * the specified dimensions. They are removed using
1305 * isl_set_project_out instead of isl_set_drop.
1306 */
1307 __isl_give PW *FN(PW,project_out)(__isl_take PW *pw,
1308 enum isl_dim_type type, unsigned first, unsigned n)
1309 {
1310 int i;
1311 enum isl_dim_type set_type;
1312
1313 if (!pw)
1314 return NULL;
1315 if (n == 0 && !isl_space_get_tuple_name(pw->dim, type))
1316 return pw;
1317
1318 set_type = type == isl_dim_in ? isl_dim_set : type;
1319
1320 pw = FN(PW,cow)(pw);
1321 if (!pw)
1322 return NULL;
1323 pw->dim = isl_space_drop_dims(pw->dim, type, first, n);
1324 if (!pw->dim)
1325 goto error;
1326 for (i = 0; i < pw->n; ++i) {
1327 pw->p[i].set = isl_set_project_out(pw->p[i].set,
1328 set_type, first, n);
1329 if (!pw->p[i].set)
1330 goto error;
1331 pw->p[i].FIELD = FN(EL,drop_dims)(pw->p[i].FIELD, type, first, n);
1332 if (!pw->p[i].FIELD)
1333 goto error;
1334 }
1335
1336 return pw;
1337 error:
1338 FN(PW,free)(pw);
1339 return NULL;
1340 }
1341
1342 /* Project the domain of pw onto its parameter space.
1343 */
1344 __isl_give PW *FN(PW,project_domain_on_params)(__isl_take PW *pw)
1345 {
1346 isl_space *space;
1347 isl_size n;
1348
1349 n = FN(PW,dim)(pw, isl_dim_in);
1350 if (n < 0)
1351 return FN(PW,free)(pw);
1352 pw = FN(PW,project_out)(pw, isl_dim_in, 0, n);
1353 space = FN(PW,get_domain_space)(pw);
1354 space = isl_space_params(space);
1355 pw = FN(PW,reset_domain_space)(pw, space);
1356 return pw;
1357 }
1358
1359 /* Drop all parameters not referenced by "pw".
1360 */
1361 __isl_give PW *FN(PW,drop_unused_params)(__isl_take PW *pw)
1362 {
1363 isl_size n;
1364 int i;
1365
1366 if (FN(PW,check_named_params)(pw) < 0)
1367 return FN(PW,free)(pw);
1368
1369 n = FN(PW,dim)(pw, isl_dim_param);
1370 if (n < 0)
1371 return FN(PW,free)(pw);
1372 for (i = n - 1; i >= 0; i--) {
1373 isl_bool involves;
1374
1375 involves = FN(PW,involves_dims)(pw, isl_dim_param, i, 1);
1376 if (involves < 0)
1377 return FN(PW,free)(pw);
1378 if (!involves)
1379 pw = FN(PW,drop_dims)(pw, isl_dim_param, i, 1);
1380 }
1381
1382 return pw;
1383 }
1384
1385 #ifndef NO_INSERT_DIMS
1386 __isl_give PW *FN(PW,insert_dims)(__isl_take PW *pw, enum isl_dim_type type,
1387 unsigned first, unsigned n)
1388 {
1389 int i;
1390 enum isl_dim_type set_type;
1391
1392 if (!pw)
1393 return NULL;
1394 if (n == 0 && !isl_space_is_named_or_nested(pw->dim, type))
1395 return pw;
1396
1397 set_type = type == isl_dim_in ? isl_dim_set : type;
1398
1399 pw = FN(PW,cow)(pw);
1400 if (!pw)
1401 return NULL;
1402
1403 pw->dim = isl_space_insert_dims(pw->dim, type, first, n);
1404 if (!pw->dim)
1405 goto error;
1406
1407 for (i = 0; i < pw->n; ++i) {
1408 pw->p[i].set = isl_set_insert_dims(pw->p[i].set,
1409 set_type, first, n);
1410 if (!pw->p[i].set)
1411 goto error;
1412 pw->p[i].FIELD = FN(EL,insert_dims)(pw->p[i].FIELD,
1413 type, first, n);
1414 if (!pw->p[i].FIELD)
1415 goto error;
1416 }
1417
1418 return pw;
1419 error:
1420 FN(PW,free)(pw);
1421 return NULL;
1422 }
1423 #endif
1424
1425 __isl_give PW *FN(PW,fix_dim)(__isl_take PW *pw,
1426 enum isl_dim_type type, unsigned pos, isl_int v)
1427 {
1428 int i;
1429
1430 if (!pw)
1431 return NULL;
1432
1433 if (type == isl_dim_in)
1434 type = isl_dim_set;
1435
1436 pw = FN(PW,cow)(pw);
1437 if (!pw)
1438 return NULL;
1439 for (i = 0; i < pw->n; ++i) {
1440 pw->p[i].set = isl_set_fix(pw->p[i].set, type, pos, v);
1441 if (FN(PW,exploit_equalities_and_remove_if_empty)(pw, i) < 0)
1442 return FN(PW,free)(pw);
1443 }
1444
1445 return pw;
1446 }
1447
1448 /* Fix the value of the variable at position "pos" of type "type" of "pw"
1449 * to be equal to "v".
1450 */
1451 __isl_give PW *FN(PW,fix_val)(__isl_take PW *pw,
1452 enum isl_dim_type type, unsigned pos, __isl_take isl_val *v)
1453 {
1454 if (!v)
1455 return FN(PW,free)(pw);
1456 if (!isl_val_is_int(v))
1457 isl_die(FN(PW,get_ctx)(pw), isl_error_invalid,
1458 "expecting integer value", goto error);
1459
1460 pw = FN(PW,fix_dim)(pw, type, pos, v->n);
1461 isl_val_free(v);
1462
1463 return pw;
1464 error:
1465 isl_val_free(v);
1466 return FN(PW,free)(pw);
1467 }
1468
1469 isl_size FN(PW,dim)(__isl_keep PW *pw, enum isl_dim_type type)
1470 {
1471 return isl_space_dim(FN(PW,peek_space)(pw), type);
1472 }
1473
1474 __isl_give PW *FN(PW,split_dims)(__isl_take PW *pw,
1475 enum isl_dim_type type, unsigned first, unsigned n)
1476 {
1477 int i;
1478
1479 if (!pw)
1480 return NULL;
1481 if (n == 0)
1482 return pw;
1483
1484 if (type == isl_dim_in)
1485 type = isl_dim_set;
1486
1487 pw = FN(PW,cow)(pw);
1488 if (!pw)
1489 return NULL;
1490 if (!pw->dim)
1491 goto error;
1492 for (i = 0; i < pw->n; ++i) {
1493 pw->p[i].set = isl_set_split_dims(pw->p[i].set, type, first, n);
1494 if (!pw->p[i].set)
1495 goto error;
1496 }
1497
1498 return pw;
1499 error:
1500 FN(PW,free)(pw);
1501 return NULL;
1502 }
1503
1504 #ifndef NO_OPT
1505 /* Compute the maximal value attained by the piecewise quasipolynomial
1506 * on its domain or zero if the domain is empty.
1507 * In the worst case, the domain is scanned completely,
1508 * so the domain is assumed to be bounded.
1509 */
1510 __isl_give isl_val *FN(PW,opt)(__isl_take PW *pw, int max)
1511 {
1512 int i;
1513 isl_val *opt;
1514
1515 if (!pw)
1516 return NULL;
1517
1518 if (pw->n == 0) {
1519 opt = isl_val_zero(FN(PW,get_ctx)(pw));
1520 FN(PW,free)(pw);
1521 return opt;
1522 }
1523
1524 opt = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[0].FIELD),
1525 isl_set_copy(pw->p[0].set), max);
1526 for (i = 1; i < pw->n; ++i) {
1527 isl_val *opt_i;
1528 opt_i = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[i].FIELD),
1529 isl_set_copy(pw->p[i].set), max);
1530 if (max)
1531 opt = isl_val_max(opt, opt_i);
1532 else
1533 opt = isl_val_min(opt, opt_i);
1534 }
1535
1536 FN(PW,free)(pw);
1537 return opt;
1538 }
1539
1540 __isl_give isl_val *FN(PW,max)(__isl_take PW *pw)
1541 {
1542 return FN(PW,opt)(pw, 1);
1543 }
1544
1545 __isl_give isl_val *FN(PW,min)(__isl_take PW *pw)
1546 {
1547 return FN(PW,opt)(pw, 0);
1548 }
1549 #endif
1550
1551 /* Return the space of "pw".
1552 */
1553 __isl_keep isl_space *FN(PW,peek_space)(__isl_keep PW *pw)
1554 {
1555 return pw ? pw->dim : NULL;
1556 }
1557
1558 __isl_give isl_space *FN(PW,get_space)(__isl_keep PW *pw)
1559 {
1560 return isl_space_copy(FN(PW,peek_space)(pw));
1561 }
1562
1563 /* Return the space of "pw".
1564 * This may be either a copy or the space itself
1565 * if there is only one reference to "pw".
1566 * This allows the space to be modified inplace
1567 * if both the piecewise expression and its space have only a single reference.
1568 * The caller is not allowed to modify "pw" between this call and
1569 * a subsequent call to isl_pw_*_restore_*.
1570 * The only exception is that isl_pw_*_free can be called instead.
1571 */
1572 __isl_give isl_space *FN(PW,take_space)(__isl_keep PW *pw)
1573 {
1574 isl_space *space;
1575
1576 if (!pw)
1577 return NULL;
1578 if (pw->ref != 1)
1579 return FN(PW,get_space)(pw);
1580 space = pw->dim;
1581 pw->dim = NULL;
1582 return space;
1583 }
1584
1585 /* Set the space of "pw" to "space", where the space of "pw" may be missing
1586 * due to a preceding call to isl_pw_*_take_space.
1587 * However, in this case, "pw" only has a single reference and
1588 * then the call to isl_pw_*_cow has no effect.
1589 */
1590 __isl_give PW *FN(PW,restore_space)(__isl_take PW *pw,
1591 __isl_take isl_space *space)
1592 {
1593 if (!pw || !space)
1594 goto error;
1595
1596 if (pw->dim == space) {
1597 isl_space_free(space);
1598 return pw;
1599 }
1600
1601 pw = FN(PW,cow)(pw);
1602 if (!pw)
1603 goto error;
1604 isl_space_free(pw->dim);
1605 pw->dim = space;
1606
1607 return pw;
1608 error:
1609 FN(PW,free)(pw);
1610 isl_space_free(space);
1611 return NULL;
1612 }
1613
1614 /* Check that "pos" is a valid position for a cell in "pw".
1615 */
1616 static isl_stat FN(PW,check_pos)(__isl_keep PW *pw, int pos)
1617 {
1618 if (!pw)
1619 return isl_stat_error;
1620 if (pos < 0 || pos >= pw->n)
1621 isl_die(FN(PW,get_ctx)(pw), isl_error_internal,
1622 "position out of bounds", return isl_stat_error);
1623 return isl_stat_ok;
1624 }
1625
1626 /* Return the cell at position "pos" in "pw".
1627 */
1628 static __isl_keep isl_set *FN(PW,peek_domain_at)(__isl_keep PW *pw, int pos)
1629 {
1630 if (FN(PW,check_pos)(pw, pos) < 0)
1631 return NULL;
1632 return pw->p[pos].set;
1633 }
1634
1635 /* Return a copy of the base expression associated to
1636 * the cell at position "pos" in "pw".
1637 */
1638 __isl_give EL *FN(PW,get_base_at)(__isl_keep PW *pw, int pos)
1639 {
1640 if (FN(PW,check_pos)(pw, pos) < 0)
1641 return NULL;
1642 return FN(EL,copy)(pw->p[pos].FIELD);
1643 }
1644
1645 /* Return the base expression associated to
1646 * the cell at position "pos" in "pw".
1647 * This may be either a copy or the base expression itself
1648 * if there is only one reference to "pw".
1649 * This allows the base expression to be modified inplace
1650 * if both the piecewise expression and this base expression
1651 * have only a single reference.
1652 * The caller is not allowed to modify "pw" between this call and
1653 * a subsequent call to isl_pw_*_restore_*.
1654 * The only exception is that isl_pw_*_free can be called instead.
1655 */
1656 __isl_give EL *FN(PW,take_base_at)(__isl_keep PW *pw, int pos)
1657 {
1658 EL *el;
1659
1660 if (!pw)
1661 return NULL;
1662 if (pw->ref != 1)
1663 return FN(PW,get_base_at)(pw, pos);
1664 if (FN(PW,check_pos)(pw, pos) < 0)
1665 return NULL;
1666 el = pw->p[pos].FIELD;
1667 pw->p[pos].FIELD = NULL;
1668 return el;
1669 }
1670
1671 /* Set the base expression associated to
1672 * the cell at position "pos" in "pw" to "el",
1673 * where this base expression may be missing
1674 * due to a preceding call to isl_pw_*_take_base_at.
1675 * However, in this case, "pw" only has a single reference and
1676 * then the call to isl_pw_*_cow has no effect.
1677 */
1678 __isl_give PW *FN(PW,restore_base_at)(__isl_take PW *pw, int pos,
1679 __isl_take EL *el)
1680 {
1681 if (FN(PW,check_pos)(pw, pos) < 0 || !el)
1682 goto error;
1683
1684 if (pw->p[pos].FIELD == el) {
1685 FN(EL,free)(el);
1686 return pw;
1687 }
1688
1689 pw = FN(PW,cow)(pw);
1690 if (!pw)
1691 goto error;
1692 FN(EL,free)(pw->p[pos].FIELD);
1693 pw->p[pos].FIELD = el;
1694
1695 return pw;
1696 error:
1697 FN(PW,free)(pw);
1698 FN(EL,free)(el);
1699 return NULL;
1700 }
1701
1702 __isl_give isl_space *FN(PW,get_domain_space)(__isl_keep PW *pw)
1703 {
1704 return pw ? isl_space_domain(isl_space_copy(pw->dim)) : NULL;
1705 }
1706
1707 /* Return the position of the dimension of the given type and name
1708 * in "pw".
1709 * Return -1 if no such dimension can be found.
1710 */
1711 int FN(PW,find_dim_by_name)(__isl_keep PW *pw,
1712 enum isl_dim_type type, const char *name)
1713 {
1714 if (!pw)
1715 return -1;
1716 return isl_space_find_dim_by_name(pw->dim, type, name);
1717 }
1718
1719 /* Return the position of the dimension of the given type and identifier
1720 * in "pw".
1721 * Return -1 if no such dimension can be found.
1722 */
1723 static int FN(PW,find_dim_by_id)(__isl_keep PW *pw,
1724 enum isl_dim_type type, __isl_keep isl_id *id)
1725 {
1726 isl_space *space;
1727
1728 space = FN(PW,peek_space)(pw);
1729 return isl_space_find_dim_by_id(space, type, id);
1730 }
1731
1732 /* Does the piecewise expression "pw" depend in any way
1733 * on the parameter with identifier "id"?
1734 */
1735 isl_bool FN(PW,involves_param_id)(__isl_keep PW *pw, __isl_keep isl_id *id)
1736 {
1737 int pos;
1738
1739 if (!pw || !id)
1740 return isl_bool_error;
1741 if (pw->n == 0)
1742 return isl_bool_false;
1743
1744 pos = FN(PW,find_dim_by_id)(pw, isl_dim_param, id);
1745 if (pos < 0)
1746 return isl_bool_false;
1747 return FN(PW,involves_dims)(pw, isl_dim_param, pos, 1);
1748 }
1749
1750 #ifndef NO_RESET_DIM
1751 /* Reset the space of "pw". Since we don't know if the elements
1752 * represent the spaces themselves or their domains, we pass along
1753 * both when we call their reset_space_and_domain.
1754 */
1755 static __isl_give PW *FN(PW,reset_space_and_domain)(__isl_take PW *pw,
1756 __isl_take isl_space *space, __isl_take isl_space *domain)
1757 {
1758 int i;
1759
1760 pw = FN(PW,cow)(pw);
1761 if (!pw || !space || !domain)
1762 goto error;
1763
1764 for (i = 0; i < pw->n; ++i) {
1765 pw->p[i].set = isl_set_reset_space(pw->p[i].set,
1766 isl_space_copy(domain));
1767 if (!pw->p[i].set)
1768 goto error;
1769 pw->p[i].FIELD = FN(EL,reset_space_and_domain)(pw->p[i].FIELD,
1770 isl_space_copy(space), isl_space_copy(domain));
1771 if (!pw->p[i].FIELD)
1772 goto error;
1773 }
1774
1775 isl_space_free(domain);
1776
1777 isl_space_free(pw->dim);
1778 pw->dim = space;
1779
1780 return pw;
1781 error:
1782 isl_space_free(domain);
1783 isl_space_free(space);
1784 FN(PW,free)(pw);
1785 return NULL;
1786 }
1787
1788 __isl_give PW *FN(PW,reset_domain_space)(__isl_take PW *pw,
1789 __isl_take isl_space *domain)
1790 {
1791 isl_space *space;
1792
1793 space = isl_space_extend_domain_with_range(isl_space_copy(domain),
1794 FN(PW,get_space)(pw));
1795 return FN(PW,reset_space_and_domain)(pw, space, domain);
1796 }
1797
1798 __isl_give PW *FN(PW,reset_space)(__isl_take PW *pw, __isl_take isl_space *dim)
1799 {
1800 isl_space *domain;
1801
1802 domain = isl_space_domain(isl_space_copy(dim));
1803 return FN(PW,reset_space_and_domain)(pw, dim, domain);
1804 }
1805
1806 __isl_give PW *FN(PW,set_tuple_id)(__isl_take PW *pw, enum isl_dim_type type,
1807 __isl_take isl_id *id)
1808 {
1809 isl_space *space;
1810
1811 pw = FN(PW,cow)(pw);
1812 if (!pw)
1813 goto error;
1814
1815 space = FN(PW,get_space)(pw);
1816 space = isl_space_set_tuple_id(space, type, id);
1817
1818 return FN(PW,reset_space)(pw, space);
1819 error:
1820 isl_id_free(id);
1821 return FN(PW,free)(pw);
1822 }
1823
1824 /* Drop the id on the specified tuple.
1825 */
1826 __isl_give PW *FN(PW,reset_tuple_id)(__isl_take PW *pw, enum isl_dim_type type)
1827 {
1828 isl_space *space;
1829
1830 if (!pw)
1831 return NULL;
1832 if (!FN(PW,has_tuple_id)(pw, type))
1833 return pw;
1834
1835 pw = FN(PW,cow)(pw);
1836 if (!pw)
1837 return NULL;
1838
1839 space = FN(PW,get_space)(pw);
1840 space = isl_space_reset_tuple_id(space, type);
1841
1842 return FN(PW,reset_space)(pw, space);
1843 }
1844
1845 __isl_give PW *FN(PW,set_dim_id)(__isl_take PW *pw,
1846 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
1847 {
1848 pw = FN(PW,cow)(pw);
1849 if (!pw)
1850 goto error;
1851 pw->dim = isl_space_set_dim_id(pw->dim, type, pos, id);
1852 return FN(PW,reset_space)(pw, isl_space_copy(pw->dim));
1853 error:
1854 isl_id_free(id);
1855 return FN(PW,free)(pw);
1856 }
1857 #endif
1858
1859 /* Reset the user pointer on all identifiers of parameters and tuples
1860 * of the space of "pw".
1861 */
1862 __isl_give PW *FN(PW,reset_user)(__isl_take PW *pw)
1863 {
1864 isl_space *space;
1865
1866 space = FN(PW,get_space)(pw);
1867 space = isl_space_reset_user(space);
1868
1869 return FN(PW,reset_space)(pw, space);
1870 }
1871
1872 isl_bool FN(PW,has_equal_space)(__isl_keep PW *pw1, __isl_keep PW *pw2)
1873 {
1874 if (!pw1 || !pw2)
1875 return isl_bool_error;
1876
1877 return isl_space_is_equal(pw1->dim, pw2->dim);
1878 }
1879
1880 isl_size FN(PW,n_piece)(__isl_keep PW *pw)
1881 {
1882 return pw ? pw->n : isl_size_error;
1883 }
1884
1885 isl_stat FN(PW,foreach_piece)(__isl_keep PW *pw,
1886 isl_stat (*fn)(__isl_take isl_set *set, __isl_take EL *el, void *user),
1887 void *user)
1888 {
1889 int i;
1890
1891 if (!pw)
1892 return isl_stat_error;
1893
1894 for (i = 0; i < pw->n; ++i)
1895 if (fn(isl_set_copy(pw->p[i].set),
1896 FN(EL,copy)(pw->p[i].FIELD), user) < 0)
1897 return isl_stat_error;
1898
1899 return isl_stat_ok;
1900 }
1901
1902 /* Is "pw" defined over a single universe domain?
1903 *
1904 * If the default value of this piecewise type is zero,
1905 * then a "pw" with a zero number of cells is also accepted
1906 * as it represents the default zero value.
1907 */
1908 isl_bool FN(FN(PW,isa),BASE)(__isl_keep PW *pw)
1909 {
1910 isl_size n;
1911
1912 n = FN(PW,n_piece)(pw);
1913 if (n < 0)
1914 return isl_bool_error;
1915 if (DEFAULT_IS_ZERO && n == 0)
1916 return isl_bool_true;
1917 if (n != 1)
1918 return isl_bool_false;
1919 return isl_set_plain_is_universe(FN(PW,peek_domain_at)(pw, 0));
1920 }
1921
1922 /* Return a zero base expression in the same space (and of the same type)
1923 * as "pw".
1924 */
1925 static __isl_give EL *FN(EL,zero_like_type)(__isl_take PW *pw OPT_TYPE_PARAM)
1926 {
1927 isl_space *space;
1928
1929 space = FN(PW,get_space)(pw);
1930 FN(PW,free)(pw);
1931 return FN(EL,zero_in_space)(space OPT_TYPE_ARG(NO_LOC));
1932 }
1933
1934 #ifndef HAS_TYPE
1935 /* Return a zero base expression in the same space as "pw".
1936 */
1937 static __isl_give EL *FN(EL,zero_like)(__isl_take PW *pw)
1938 {
1939 return FN(EL,zero_like_type)(pw);
1940 }
1941 #else
1942 /* Return a zero base expression in the same space and of the same type
1943 * as "pw".
1944 *
1945 * Pass along the type as an explicit argument for uniform handling
1946 * in isl_*_zero_like_type.
1947 */
1948 static __isl_give EL *FN(EL,zero_like)(__isl_take PW *pw)
1949 {
1950 enum isl_fold type;
1951
1952 type = FN(PW,get_type)(pw);
1953 if (type < 0)
1954 goto error;
1955 return FN(EL,zero_like_type)(pw, type);
1956 error:
1957 FN(PW,free)(pw);
1958 return NULL;
1959 }
1960 #endif
1961
1962 /* Given that "pw" is defined over a single universe domain,
1963 * return the base expression associated to this domain.
1964 *
1965 * If the number of cells is zero, then "pw" is of a piecewise type
1966 * with a default zero value and effectively represents zero.
1967 * In this case, create a zero base expression in the same space
1968 * (and with the same type).
1969 * Otherwise, simply extract the associated base expression.
1970 */
1971 __isl_give EL *FN(FN(PW,as),BASE)(__isl_take PW *pw)
1972 {
1973 isl_bool is_total;
1974 isl_size n;
1975 EL *el;
1976
1977 is_total = FN(FN(PW,isa),BASE)(pw);
1978 if (is_total < 0)
1979 goto error;
1980 if (!is_total)
1981 isl_die(FN(PW,get_ctx)(pw), isl_error_invalid,
1982 "expecting single total function", goto error);
1983 n = FN(PW,n_piece)(pw);
1984 if (n < 0)
1985 goto error;
1986 if (n == 0)
1987 return FN(EL,zero_like)(pw);
1988 el = FN(PW,take_base_at)(pw, 0);
1989 FN(PW,free)(pw);
1990 return el;
1991 error:
1992 FN(PW,free)(pw);
1993 return NULL;
1994 }
1995
1996 #ifndef NO_LIFT
1997 static isl_bool any_divs(__isl_keep isl_set *set)
1998 {
1999 int i;
2000
2001 if (!set)
2002 return isl_bool_error;
2003
2004 for (i = 0; i < set->n; ++i)
2005 if (set->p[i]->n_div > 0)
2006 return isl_bool_true;
2007
2008 return isl_bool_false;
2009 }
2010
2011 static isl_stat foreach_lifted_subset(__isl_take isl_set *set,
2012 __isl_take EL *el,
2013 isl_stat (*fn)(__isl_take isl_set *set, __isl_take EL *el,
2014 void *user), void *user)
2015 {
2016 int i;
2017
2018 if (!set || !el)
2019 goto error;
2020
2021 for (i = 0; i < set->n; ++i) {
2022 isl_set *lift;
2023 EL *copy;
2024
2025 lift = isl_set_from_basic_set(isl_basic_set_copy(set->p[i]));
2026 lift = isl_set_lift(lift);
2027
2028 copy = FN(EL,copy)(el);
2029 copy = FN(EL,lift)(copy, isl_set_get_space(lift));
2030
2031 if (fn(lift, copy, user) < 0)
2032 goto error;
2033 }
2034
2035 isl_set_free(set);
2036 FN(EL,free)(el);
2037
2038 return isl_stat_ok;
2039 error:
2040 isl_set_free(set);
2041 FN(EL,free)(el);
2042 return isl_stat_error;
2043 }
2044
2045 isl_stat FN(PW,foreach_lifted_piece)(__isl_keep PW *pw,
2046 isl_stat (*fn)(__isl_take isl_set *set, __isl_take EL *el,
2047 void *user), void *user)
2048 {
2049 int i;
2050
2051 if (!pw)
2052 return isl_stat_error;
2053
2054 for (i = 0; i < pw->n; ++i) {
2055 isl_bool any;
2056 isl_set *set;
2057 EL *el;
2058
2059 any = any_divs(pw->p[i].set);
2060 if (any < 0)
2061 return isl_stat_error;
2062 set = isl_set_copy(pw->p[i].set);
2063 el = FN(EL,copy)(pw->p[i].FIELD);
2064 if (!any) {
2065 if (fn(set, el, user) < 0)
2066 return isl_stat_error;
2067 continue;
2068 }
2069 if (foreach_lifted_subset(set, el, fn, user) < 0)
2070 return isl_stat_error;
2071 }
2072
2073 return isl_stat_ok;
2074 }
2075 #endif
2076
2077 #ifndef NO_MOVE_DIMS
2078 __isl_give PW *FN(PW,move_dims)(__isl_take PW *pw,
2079 enum isl_dim_type dst_type, unsigned dst_pos,
2080 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
2081 {
2082 int i;
2083
2084 pw = FN(PW,cow)(pw);
2085 if (!pw)
2086 return NULL;
2087
2088 pw->dim = isl_space_move_dims(pw->dim, dst_type, dst_pos, src_type, src_pos, n);
2089 if (!pw->dim)
2090 goto error;
2091
2092 for (i = 0; i < pw->n; ++i) {
2093 pw->p[i].FIELD = FN(EL,move_dims)(pw->p[i].FIELD,
2094 dst_type, dst_pos, src_type, src_pos, n);
2095 if (!pw->p[i].FIELD)
2096 goto error;
2097 }
2098
2099 if (dst_type == isl_dim_in)
2100 dst_type = isl_dim_set;
2101 if (src_type == isl_dim_in)
2102 src_type = isl_dim_set;
2103
2104 for (i = 0; i < pw->n; ++i) {
2105 pw->p[i].set = isl_set_move_dims(pw->p[i].set,
2106 dst_type, dst_pos,
2107 src_type, src_pos, n);
2108 if (!pw->p[i].set)
2109 goto error;
2110 }
2111
2112 return pw;
2113 error:
2114 FN(PW,free)(pw);
2115 return NULL;
2116 }
2117 #endif
2118
2119 #ifdef HAS_TYPE
2120 /* Negate the type of "pw".
2121 */
2122 static __isl_give PW *FN(PW,negate_type)(__isl_take PW *pw)
2123 {
2124 pw = FN(PW,cow)(pw);
2125 if (!pw)
2126 return NULL;
2127 pw->type = isl_fold_type_negate(pw->type);
2128 return pw;
2129 }
2130 #else
2131 /* Negate the type of "pw".
2132 * Since "pw" does not have a type, do nothing.
2133 */
2134 static __isl_give PW *FN(PW,negate_type)(__isl_take PW *pw)
2135 {
2136 return pw;
2137 }
2138 #endif
2139
2140 __isl_give PW *FN(PW,mul_isl_int)(__isl_take PW *pw, isl_int v)
2141 {
2142 int i;
2143
2144 if (isl_int_is_one(v))
2145 return pw;
2146 if (pw && DEFAULT_IS_ZERO && isl_int_is_zero(v)) {
2147 PW *zero;
2148 isl_space *dim = FN(PW,get_space)(pw);
2149 zero = FN(PW,ZERO)(dim OPT_TYPE_ARG(pw->));
2150 FN(PW,free)(pw);
2151 return zero;
2152 }
2153 pw = FN(PW,cow)(pw);
2154 if (isl_int_is_neg(v))
2155 pw = FN(PW,negate_type)(pw);
2156 if (!pw)
2157 return NULL;
2158 if (pw->n == 0)
2159 return pw;
2160
2161 for (i = 0; i < pw->n; ++i) {
2162 pw->p[i].FIELD = FN(EL,scale)(pw->p[i].FIELD, v);
2163 if (!pw->p[i].FIELD)
2164 goto error;
2165 }
2166
2167 return pw;
2168 error:
2169 FN(PW,free)(pw);
2170 return NULL;
2171 }
2172
2173 /* Multiply the pieces of "pw" by "v" and return the result.
2174 */
2175 __isl_give PW *FN(PW,scale_val)(__isl_take PW *pw, __isl_take isl_val *v)
2176 {
2177 int i;
2178
2179 if (!pw || !v)
2180 goto error;
2181
2182 if (isl_val_is_one(v)) {
2183 isl_val_free(v);
2184 return pw;
2185 }
2186 if (pw && DEFAULT_IS_ZERO && isl_val_is_zero(v)) {
2187 PW *zero;
2188 isl_space *space = FN(PW,get_space)(pw);
2189 zero = FN(PW,ZERO)(space OPT_TYPE_ARG(pw->));
2190 FN(PW,free)(pw);
2191 isl_val_free(v);
2192 return zero;
2193 }
2194 if (pw->n == 0) {
2195 isl_val_free(v);
2196 return pw;
2197 }
2198 pw = FN(PW,cow)(pw);
2199 if (isl_val_is_neg(v))
2200 pw = FN(PW,negate_type)(pw);
2201 if (!pw)
2202 goto error;
2203
2204 for (i = 0; i < pw->n; ++i) {
2205 pw->p[i].FIELD = FN(EL,scale_val)(pw->p[i].FIELD,
2206 isl_val_copy(v));
2207 if (!pw->p[i].FIELD)
2208 goto error;
2209 }
2210
2211 isl_val_free(v);
2212 return pw;
2213 error:
2214 isl_val_free(v);
2215 FN(PW,free)(pw);
2216 return NULL;
2217 }
2218
2219 /* Divide the pieces of "pw" by "v" and return the result.
2220 */
2221 __isl_give PW *FN(PW,scale_down_val)(__isl_take PW *pw, __isl_take isl_val *v)
2222 {
2223 int i;
2224
2225 if (!pw || !v)
2226 goto error;
2227
2228 if (isl_val_is_one(v)) {
2229 isl_val_free(v);
2230 return pw;
2231 }
2232
2233 if (!isl_val_is_rat(v))
2234 isl_die(isl_val_get_ctx(v), isl_error_invalid,
2235 "expecting rational factor", goto error);
2236 if (isl_val_is_zero(v))
2237 isl_die(isl_val_get_ctx(v), isl_error_invalid,
2238 "cannot scale down by zero", goto error);
2239
2240 if (pw->n == 0) {
2241 isl_val_free(v);
2242 return pw;
2243 }
2244 pw = FN(PW,cow)(pw);
2245 if (isl_val_is_neg(v))
2246 pw = FN(PW,negate_type)(pw);
2247 if (!pw)
2248 goto error;
2249
2250 for (i = 0; i < pw->n; ++i) {
2251 pw->p[i].FIELD = FN(EL,scale_down_val)(pw->p[i].FIELD,
2252 isl_val_copy(v));
2253 if (!pw->p[i].FIELD)
2254 goto error;
2255 }
2256
2257 isl_val_free(v);
2258 return pw;
2259 error:
2260 isl_val_free(v);
2261 FN(PW,free)(pw);
2262 return NULL;
2263 }
2264
2265 __isl_give PW *FN(PW,scale)(__isl_take PW *pw, isl_int v)
2266 {
2267 return FN(PW,mul_isl_int)(pw, v);
2268 }
2269
2270 /* Apply some normalization to "pw".
2271 * In particular, sort the pieces according to their function value
2272 * expressions, combining pairs of adjacent pieces with
2273 * the same such expression, and then normalize the domains of the pieces.
2274 *
2275 * We normalize in place, but if anything goes wrong we need
2276 * to return NULL, so we need to make sure we don't change the
2277 * meaning of any possible other copies of "pw".
2278 */
2279 __isl_give PW *FN(PW,normalize)(__isl_take PW *pw)
2280 {
2281 int i;
2282 isl_set *set;
2283
2284 pw = FN(PW,sort)(pw);
2285 if (!pw)
2286 return NULL;
2287 for (i = 0; i < pw->n; ++i) {
2288 set = isl_set_normalize(isl_set_copy(pw->p[i].set));
2289 if (!set)
2290 return FN(PW,free)(pw);
2291 isl_set_free(pw->p[i].set);
2292 pw->p[i].set = set;
2293 }
2294
2295 return pw;
2296 }
2297
2298 /* Is pw1 obviously equal to pw2?
2299 * That is, do they have obviously identical cells and obviously identical
2300 * elements on each cell?
2301 *
2302 * If "pw1" or "pw2" contain any NaNs, then they are considered
2303 * not to be the same. A NaN is not equal to anything, not even
2304 * to another NaN.
2305 */
2306 isl_bool FN(PW,plain_is_equal)(__isl_keep PW *pw1, __isl_keep PW *pw2)
2307 {
2308 int i;
2309 isl_bool equal, has_nan;
2310
2311 if (!pw1 || !pw2)
2312 return isl_bool_error;
2313
2314 has_nan = FN(PW,involves_nan)(pw1);
2315 if (has_nan >= 0 && !has_nan)
2316 has_nan = FN(PW,involves_nan)(pw2);
2317 if (has_nan < 0 || has_nan)
2318 return isl_bool_not(has_nan);
2319
2320 if (pw1 == pw2)
2321 return isl_bool_true;
2322 if (!isl_space_is_equal(pw1->dim, pw2->dim))
2323 return isl_bool_false;
2324
2325 pw1 = FN(PW,copy)(pw1);
2326 pw2 = FN(PW,copy)(pw2);
2327 pw1 = FN(PW,normalize)(pw1);
2328 pw2 = FN(PW,normalize)(pw2);
2329 if (!pw1 || !pw2)
2330 goto error;
2331
2332 equal = isl_bool_ok(pw1->n == pw2->n);
2333 for (i = 0; equal && i < pw1->n; ++i) {
2334 equal = isl_set_plain_is_equal(pw1->p[i].set, pw2->p[i].set);
2335 if (equal < 0)
2336 goto error;
2337 if (!equal)
2338 break;
2339 equal = FN(EL,plain_is_equal)(pw1->p[i].FIELD, pw2->p[i].FIELD);
2340 if (equal < 0)
2341 goto error;
2342 }
2343
2344 FN(PW,free)(pw1);
2345 FN(PW,free)(pw2);
2346 return equal;
2347 error:
2348 FN(PW,free)(pw1);
2349 FN(PW,free)(pw2);
2350 return isl_bool_error;
2351 }
2352
2353 /* Does "pw" involve any NaNs?
2354 */
2355 isl_bool FN(PW,involves_nan)(__isl_keep PW *pw)
2356 {
2357 int i;
2358
2359 if (!pw)
2360 return isl_bool_error;
2361 if (pw->n == 0)
2362 return isl_bool_false;
2363
2364 for (i = 0; i < pw->n; ++i) {
2365 isl_bool has_nan = FN(EL,involves_nan)(pw->p[i].FIELD);
2366 if (has_nan < 0 || has_nan)
2367 return has_nan;
2368 }
2369
2370 return isl_bool_false;
2371 }
2372
2373 #ifndef NO_PULLBACK
2374 static __isl_give PW *FN(PW,align_params_pw_multi_aff_and)(__isl_take PW *pw,
2375 __isl_take isl_multi_aff *ma,
2376 __isl_give PW *(*fn)(__isl_take PW *pw, __isl_take isl_multi_aff *ma))
2377 {
2378 isl_ctx *ctx;
2379 isl_bool equal_params;
2380 isl_space *ma_space;
2381
2382 ma_space = isl_multi_aff_get_space(ma);
2383 if (!pw || !ma || !ma_space)
2384 goto error;
2385 equal_params = isl_space_has_equal_params(pw->dim, ma_space);
2386 if (equal_params < 0)
2387 goto error;
2388 if (equal_params) {
2389 isl_space_free(ma_space);
2390 return fn(pw, ma);
2391 }
2392 ctx = FN(PW,get_ctx)(pw);
2393 if (FN(PW,check_named_params)(pw) < 0)
2394 goto error;
2395 if (!isl_space_has_named_params(ma_space))
2396 isl_die(ctx, isl_error_invalid,
2397 "unaligned unnamed parameters", goto error);
2398 pw = FN(PW,align_params)(pw, ma_space);
2399 ma = isl_multi_aff_align_params(ma, FN(PW,get_space)(pw));
2400 return fn(pw, ma);
2401 error:
2402 isl_space_free(ma_space);
2403 FN(PW,free)(pw);
2404 isl_multi_aff_free(ma);
2405 return NULL;
2406 }
2407
2408 static __isl_give PW *FN(PW,align_params_pw_pw_multi_aff_and)(__isl_take PW *pw,
2409 __isl_take isl_pw_multi_aff *pma,
2410 __isl_give PW *(*fn)(__isl_take PW *pw,
2411 __isl_take isl_pw_multi_aff *ma))
2412 {
2413 isl_bool equal_params;
2414 isl_space *pma_space;
2415
2416 pma_space = isl_pw_multi_aff_get_space(pma);
2417 if (!pw || !pma || !pma_space)
2418 goto error;
2419 equal_params = isl_space_has_equal_params(pw->dim, pma_space);
2420 if (equal_params < 0)
2421 goto error;
2422 if (equal_params) {
2423 isl_space_free(pma_space);
2424 return fn(pw, pma);
2425 }
2426 if (FN(PW,check_named_params)(pw) < 0 ||
2427 isl_pw_multi_aff_check_named_params(pma) < 0)
2428 goto error;
2429 pw = FN(PW,align_params)(pw, pma_space);
2430 pma = isl_pw_multi_aff_align_params(pma, FN(PW,get_space)(pw));
2431 return fn(pw, pma);
2432 error:
2433 isl_space_free(pma_space);
2434 FN(PW,free)(pw);
2435 isl_pw_multi_aff_free(pma);
2436 return NULL;
2437 }
2438
2439 /* Compute the pullback of "pw" by the function represented by "ma".
2440 * In other words, plug in "ma" in "pw".
2441 */
2442 static __isl_give PW *FN(PW,pullback_multi_aff_aligned)(__isl_take PW *pw,
2443 __isl_take isl_multi_aff *ma)
2444 {
2445 int i;
2446 isl_space *space = NULL;
2447
2448 ma = isl_multi_aff_align_divs(ma);
2449 pw = FN(PW,cow)(pw);
2450 if (!pw || !ma)
2451 goto error;
2452
2453 space = isl_space_join(isl_multi_aff_get_space(ma),
2454 FN(PW,get_space)(pw));
2455
2456 for (i = 0; i < pw->n; ++i) {
2457 pw->p[i].set = isl_set_preimage_multi_aff(pw->p[i].set,
2458 isl_multi_aff_copy(ma));
2459 if (!pw->p[i].set)
2460 goto error;
2461 pw->p[i].FIELD = FN(EL,pullback_multi_aff)(pw->p[i].FIELD,
2462 isl_multi_aff_copy(ma));
2463 if (!pw->p[i].FIELD)
2464 goto error;
2465 }
2466
2467 pw = FN(PW,reset_space)(pw, space);
2468 isl_multi_aff_free(ma);
2469 return pw;
2470 error:
2471 isl_space_free(space);
2472 isl_multi_aff_free(ma);
2473 FN(PW,free)(pw);
2474 return NULL;
2475 }
2476
2477 __isl_give PW *FN(PW,pullback_multi_aff)(__isl_take PW *pw,
2478 __isl_take isl_multi_aff *ma)
2479 {
2480 return FN(PW,align_params_pw_multi_aff_and)(pw, ma,
2481 &FN(PW,pullback_multi_aff_aligned));
2482 }
2483
2484 /* Compute the pullback of "pw" by the function represented by "pma".
2485 * In other words, plug in "pma" in "pw".
2486 */
2487 static __isl_give PW *FN(PW,pullback_pw_multi_aff_aligned)(__isl_take PW *pw,
2488 __isl_take isl_pw_multi_aff *pma)
2489 {
2490 int i;
2491 PW *res;
2492
2493 if (!pma)
2494 goto error;
2495
2496 if (pma->n == 0) {
2497 isl_space *space;
2498 space = isl_space_join(isl_pw_multi_aff_get_space(pma),
2499 FN(PW,get_space)(pw));
2500 isl_pw_multi_aff_free(pma);
2501 res = FN(PW,empty)(space);
2502 FN(PW,free)(pw);
2503 return res;
2504 }
2505
2506 res = FN(PW,pullback_multi_aff)(FN(PW,copy)(pw),
2507 isl_multi_aff_copy(pma->p[0].maff));
2508 res = FN(PW,intersect_domain)(res, isl_set_copy(pma->p[0].set));
2509
2510 for (i = 1; i < pma->n; ++i) {
2511 PW *res_i;
2512
2513 res_i = FN(PW,pullback_multi_aff)(FN(PW,copy)(pw),
2514 isl_multi_aff_copy(pma->p[i].maff));
2515 res_i = FN(PW,intersect_domain)(res_i,
2516 isl_set_copy(pma->p[i].set));
2517 res = FN(PW,add_disjoint)(res, res_i);
2518 }
2519
2520 isl_pw_multi_aff_free(pma);
2521 FN(PW,free)(pw);
2522 return res;
2523 error:
2524 isl_pw_multi_aff_free(pma);
2525 FN(PW,free)(pw);
2526 return NULL;
2527 }
2528
2529 __isl_give PW *FN(PW,pullback_pw_multi_aff)(__isl_take PW *pw,
2530 __isl_take isl_pw_multi_aff *pma)
2531 {
2532 return FN(PW,align_params_pw_pw_multi_aff_and)(pw, pma,
2533 &FN(PW,pullback_pw_multi_aff_aligned));
2534 }
2535 #endif
Integer set library