?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
add isl_space_range_map
[isl.git] / isl_pw_templ.c
blobc8c78946503e9172e1a7a24c872d5d7ece3a7261
1 #include <isl/aff.h>
2 #include <isl_val_private.h>
3
4 #define xFN(TYPE,NAME) TYPE ## _ ## NAME
5 #define FN(TYPE,NAME) xFN(TYPE,NAME)
6 #define xS(TYPE,NAME) struct TYPE ## _ ## NAME
7 #define S(TYPE,NAME) xS(TYPE,NAME)
8
9 #ifdef HAS_TYPE
10 __isl_give PW *FN(PW,alloc_size)(__isl_take isl_space *dim,
11 enum isl_fold type, int n)
12 #else
13 __isl_give PW *FN(PW,alloc_size)(__isl_take isl_space *dim, int n)
14 #endif
15 {
16 isl_ctx *ctx;
17 struct PW *pw;
18
19 if (!dim)
20 return NULL;
21 ctx = isl_space_get_ctx(dim);
22 isl_assert(ctx, n >= 0, goto error);
23 pw = isl_alloc(ctx, struct PW,
24 sizeof(struct PW) + (n - 1) * sizeof(S(PW,piece)));
25 if (!pw)
26 goto error;
27
28 pw->ref = 1;
29 #ifdef HAS_TYPE
30 pw->type = type;
31 #endif
32 pw->size = n;
33 pw->n = 0;
34 pw->dim = dim;
35 return pw;
36 error:
37 isl_space_free(dim);
38 return NULL;
39 }
40
41 #ifdef HAS_TYPE
42 __isl_give PW *FN(PW,ZERO)(__isl_take isl_space *dim, enum isl_fold type)
43 {
44 return FN(PW,alloc_size)(dim, type, 0);
45 }
46 #else
47 __isl_give PW *FN(PW,ZERO)(__isl_take isl_space *dim)
48 {
49 return FN(PW,alloc_size)(dim, 0);
50 }
51 #endif
52
53 __isl_give PW *FN(PW,add_piece)(__isl_take PW *pw,
54 __isl_take isl_set *set, __isl_take EL *el)
55 {
56 isl_ctx *ctx;
57 isl_space *el_dim = NULL;
58
59 if (!pw || !set || !el)
60 goto error;
61
62 if (isl_set_plain_is_empty(set) || FN(EL,EL_IS_ZERO)(el)) {
63 isl_set_free(set);
64 FN(EL,free)(el);
65 return pw;
66 }
67
68 ctx = isl_set_get_ctx(set);
69 #ifdef HAS_TYPE
70 if (pw->type != el->type)
71 isl_die(ctx, isl_error_invalid, "fold types don't match",
72 goto error);
73 #endif
74 el_dim = FN(EL,get_space(el));
75 isl_assert(ctx, isl_space_is_equal(pw->dim, el_dim), goto error);
76 isl_assert(ctx, pw->n < pw->size, goto error);
77
78 pw->p[pw->n].set = set;
79 pw->p[pw->n].FIELD = el;
80 pw->n++;
81
82 isl_space_free(el_dim);
83 return pw;
84 error:
85 isl_space_free(el_dim);
86 FN(PW,free)(pw);
87 isl_set_free(set);
88 FN(EL,free)(el);
89 return NULL;
90 }
91
92 #ifdef HAS_TYPE
93 __isl_give PW *FN(PW,alloc)(enum isl_fold type,
94 __isl_take isl_set *set, __isl_take EL *el)
95 #else
96 __isl_give PW *FN(PW,alloc)(__isl_take isl_set *set, __isl_take EL *el)
97 #endif
98 {
99 PW *pw;
100
101 if (!set || !el)
102 goto error;
103
104 #ifdef HAS_TYPE
105 pw = FN(PW,alloc_size)(FN(EL,get_space)(el), type, 1);
106 #else
107 pw = FN(PW,alloc_size)(FN(EL,get_space)(el), 1);
108 #endif
109
110 return FN(PW,add_piece)(pw, set, el);
111 error:
112 isl_set_free(set);
113 FN(EL,free)(el);
114 return NULL;
115 }
116
117 __isl_give PW *FN(PW,dup)(__isl_keep PW *pw)
118 {
119 int i;
120 PW *dup;
121
122 if (!pw)
123 return NULL;
124
125 #ifdef HAS_TYPE
126 dup = FN(PW,alloc_size)(isl_space_copy(pw->dim), pw->type, pw->n);
127 #else
128 dup = FN(PW,alloc_size)(isl_space_copy(pw->dim), pw->n);
129 #endif
130 if (!dup)
131 return NULL;
132
133 for (i = 0; i < pw->n; ++i)
134 dup = FN(PW,add_piece)(dup, isl_set_copy(pw->p[i].set),
135 FN(EL,copy)(pw->p[i].FIELD));
136
137 return dup;
138 }
139
140 __isl_give PW *FN(PW,cow)(__isl_take PW *pw)
141 {
142 if (!pw)
143 return NULL;
144
145 if (pw->ref == 1)
146 return pw;
147 pw->ref--;
148 return FN(PW,dup)(pw);
149 }
150
151 __isl_give PW *FN(PW,copy)(__isl_keep PW *pw)
152 {
153 if (!pw)
154 return NULL;
155
156 pw->ref++;
157 return pw;
158 }
159
160 void *FN(PW,free)(__isl_take PW *pw)
161 {
162 int i;
163
164 if (!pw)
165 return NULL;
166 if (--pw->ref > 0)
167 return NULL;
168
169 for (i = 0; i < pw->n; ++i) {
170 isl_set_free(pw->p[i].set);
171 FN(EL,free)(pw->p[i].FIELD);
172 }
173 isl_space_free(pw->dim);
174 free(pw);
175
176 return NULL;
177 }
178
179 const char *FN(PW,get_dim_name)(__isl_keep PW *pw, enum isl_dim_type type,
180 unsigned pos)
181 {
182 return pw ? isl_space_get_dim_name(pw->dim, type, pos) : NULL;
183 }
184
185 int FN(PW,has_dim_id)(__isl_keep PW *pw, enum isl_dim_type type, unsigned pos)
186 {
187 return pw ? isl_space_has_dim_id(pw->dim, type, pos) : -1;
188 }
189
190 __isl_give isl_id *FN(PW,get_dim_id)(__isl_keep PW *pw, enum isl_dim_type type,
191 unsigned pos)
192 {
193 return pw ? isl_space_get_dim_id(pw->dim, type, pos) : NULL;
194 }
195
196 int FN(PW,has_tuple_name)(__isl_keep PW *pw, enum isl_dim_type type)
197 {
198 return pw ? isl_space_has_tuple_name(pw->dim, type) : -1;
199 }
200
201 const char *FN(PW,get_tuple_name)(__isl_keep PW *pw, enum isl_dim_type type)
202 {
203 return pw ? isl_space_get_tuple_name(pw->dim, type) : NULL;
204 }
205
206 int FN(PW,has_tuple_id)(__isl_keep PW *pw, enum isl_dim_type type)
207 {
208 return pw ? isl_space_has_tuple_id(pw->dim, type) : -1;
209 }
210
211 __isl_give isl_id *FN(PW,get_tuple_id)(__isl_keep PW *pw, enum isl_dim_type type)
212 {
213 return pw ? isl_space_get_tuple_id(pw->dim, type) : NULL;
214 }
215
216 int FN(PW,IS_ZERO)(__isl_keep PW *pw)
217 {
218 if (!pw)
219 return -1;
220
221 return pw->n == 0;
222 }
223
224 #ifndef NO_REALIGN
225 __isl_give PW *FN(PW,realign_domain)(__isl_take PW *pw,
226 __isl_take isl_reordering *exp)
227 {
228 int i;
229
230 pw = FN(PW,cow)(pw);
231 if (!pw || !exp)
232 goto error;
233
234 for (i = 0; i < pw->n; ++i) {
235 pw->p[i].set = isl_set_realign(pw->p[i].set,
236 isl_reordering_copy(exp));
237 if (!pw->p[i].set)
238 goto error;
239 pw->p[i].FIELD = FN(EL,realign_domain)(pw->p[i].FIELD,
240 isl_reordering_copy(exp));
241 if (!pw->p[i].FIELD)
242 goto error;
243 }
244
245 pw = FN(PW,reset_domain_space)(pw, isl_space_copy(exp->dim));
246
247 isl_reordering_free(exp);
248 return pw;
249 error:
250 isl_reordering_free(exp);
251 FN(PW,free)(pw);
252 return NULL;
253 }
254
255 /* Align the parameters of "pw" to those of "model".
256 */
257 __isl_give PW *FN(PW,align_params)(__isl_take PW *pw, __isl_take isl_space *model)
258 {
259 isl_ctx *ctx;
260
261 if (!pw || !model)
262 goto error;
263
264 ctx = isl_space_get_ctx(model);
265 if (!isl_space_has_named_params(model))
266 isl_die(ctx, isl_error_invalid,
267 "model has unnamed parameters", goto error);
268 if (!isl_space_has_named_params(pw->dim))
269 isl_die(ctx, isl_error_invalid,
270 "input has unnamed parameters", goto error);
271 if (!isl_space_match(pw->dim, isl_dim_param, model, isl_dim_param)) {
272 isl_reordering *exp;
273
274 model = isl_space_drop_dims(model, isl_dim_in,
275 0, isl_space_dim(model, isl_dim_in));
276 model = isl_space_drop_dims(model, isl_dim_out,
277 0, isl_space_dim(model, isl_dim_out));
278 exp = isl_parameter_alignment_reordering(pw->dim, model);
279 exp = isl_reordering_extend_space(exp,
280 FN(PW,get_domain_space)(pw));
281 pw = FN(PW,realign_domain)(pw, exp);
282 }
283
284 isl_space_free(model);
285 return pw;
286 error:
287 isl_space_free(model);
288 FN(PW,free)(pw);
289 return NULL;
290 }
291
292 static __isl_give PW *FN(PW,align_params_pw_pw_and)(__isl_take PW *pw1,
293 __isl_take PW *pw2,
294 __isl_give PW *(*fn)(__isl_take PW *pw1, __isl_take PW *pw2))
295 {
296 isl_ctx *ctx;
297
298 if (!pw1 || !pw2)
299 goto error;
300 if (isl_space_match(pw1->dim, isl_dim_param, pw2->dim, isl_dim_param))
301 return fn(pw1, pw2);
302 ctx = FN(PW,get_ctx)(pw1);
303 if (!isl_space_has_named_params(pw1->dim) ||
304 !isl_space_has_named_params(pw2->dim))
305 isl_die(ctx, isl_error_invalid,
306 "unaligned unnamed parameters", goto error);
307 pw1 = FN(PW,align_params)(pw1, FN(PW,get_space)(pw2));
308 pw2 = FN(PW,align_params)(pw2, FN(PW,get_space)(pw1));
309 return fn(pw1, pw2);
310 error:
311 FN(PW,free)(pw1);
312 FN(PW,free)(pw2);
313 return NULL;
314 }
315
316 static __isl_give PW *FN(PW,align_params_pw_set_and)(__isl_take PW *pw,
317 __isl_take isl_set *set,
318 __isl_give PW *(*fn)(__isl_take PW *pw, __isl_take isl_set *set))
319 {
320 isl_ctx *ctx;
321
322 if (!pw || !set)
323 goto error;
324 if (isl_space_match(pw->dim, isl_dim_param, set->dim, isl_dim_param))
325 return fn(pw, set);
326 ctx = FN(PW,get_ctx)(pw);
327 if (!isl_space_has_named_params(pw->dim) ||
328 !isl_space_has_named_params(set->dim))
329 isl_die(ctx, isl_error_invalid,
330 "unaligned unnamed parameters", goto error);
331 pw = FN(PW,align_params)(pw, isl_set_get_space(set));
332 set = isl_set_align_params(set, FN(PW,get_space)(pw));
333 return fn(pw, set);
334 error:
335 FN(PW,free)(pw);
336 isl_set_free(set);
337 return NULL;
338 }
339 #endif
340
341 static __isl_give PW *FN(PW,union_add_aligned)(__isl_take PW *pw1,
342 __isl_take PW *pw2)
343 {
344 int i, j, n;
345 struct PW *res;
346 isl_ctx *ctx;
347 isl_set *set;
348
349 if (!pw1 || !pw2)
350 goto error;
351
352 ctx = isl_space_get_ctx(pw1->dim);
353 #ifdef HAS_TYPE
354 if (pw1->type != pw2->type)
355 isl_die(ctx, isl_error_invalid,
356 "fold types don't match", goto error);
357 #endif
358 isl_assert(ctx, isl_space_is_equal(pw1->dim, pw2->dim), goto error);
359
360 if (FN(PW,IS_ZERO)(pw1)) {
361 FN(PW,free)(pw1);
362 return pw2;
363 }
364
365 if (FN(PW,IS_ZERO)(pw2)) {
366 FN(PW,free)(pw2);
367 return pw1;
368 }
369
370 n = (pw1->n + 1) * (pw2->n + 1);
371 #ifdef HAS_TYPE
372 res = FN(PW,alloc_size)(isl_space_copy(pw1->dim), pw1->type, n);
373 #else
374 res = FN(PW,alloc_size)(isl_space_copy(pw1->dim), n);
375 #endif
376
377 for (i = 0; i < pw1->n; ++i) {
378 set = isl_set_copy(pw1->p[i].set);
379 for (j = 0; j < pw2->n; ++j) {
380 struct isl_set *common;
381 EL *sum;
382 common = isl_set_intersect(isl_set_copy(pw1->p[i].set),
383 isl_set_copy(pw2->p[j].set));
384 if (isl_set_plain_is_empty(common)) {
385 isl_set_free(common);
386 continue;
387 }
388 set = isl_set_subtract(set,
389 isl_set_copy(pw2->p[j].set));
390
391 sum = FN(EL,add_on_domain)(common,
392 FN(EL,copy)(pw1->p[i].FIELD),
393 FN(EL,copy)(pw2->p[j].FIELD));
394
395 res = FN(PW,add_piece)(res, common, sum);
396 }
397 res = FN(PW,add_piece)(res, set, FN(EL,copy)(pw1->p[i].FIELD));
398 }
399
400 for (j = 0; j < pw2->n; ++j) {
401 set = isl_set_copy(pw2->p[j].set);
402 for (i = 0; i < pw1->n; ++i)
403 set = isl_set_subtract(set,
404 isl_set_copy(pw1->p[i].set));
405 res = FN(PW,add_piece)(res, set, FN(EL,copy)(pw2->p[j].FIELD));
406 }
407
408 FN(PW,free)(pw1);
409 FN(PW,free)(pw2);
410
411 return res;
412 error:
413 FN(PW,free)(pw1);
414 FN(PW,free)(pw2);
415 return NULL;
416 }
417
418 /* Private version of "union_add". For isl_pw_qpolynomial and
419 * isl_pw_qpolynomial_fold, we prefer to simply call it "add".
420 */
421 static __isl_give PW *FN(PW,union_add_)(__isl_take PW *pw1, __isl_take PW *pw2)
422 {
423 return FN(PW,align_params_pw_pw_and)(pw1, pw2,
424 &FN(PW,union_add_aligned));
425 }
426
427 /* Make sure "pw" has room for at least "n" more pieces.
428 *
429 * If there is only one reference to pw, we extend it in place.
430 * Otherwise, we create a new PW and copy the pieces.
431 */
432 static __isl_give PW *FN(PW,grow)(__isl_take PW *pw, int n)
433 {
434 int i;
435 isl_ctx *ctx;
436 PW *res;
437
438 if (!pw)
439 return NULL;
440 if (pw->n + n <= pw->size)
441 return pw;
442 ctx = FN(PW,get_ctx)(pw);
443 n += pw->n;
444 if (pw->ref == 1) {
445 res = isl_realloc(ctx, pw, struct PW,
446 sizeof(struct PW) + (n - 1) * sizeof(S(PW,piece)));
447 if (!res)
448 return FN(PW,free)(pw);
449 res->size = n;
450 return res;
451 }
452 #ifdef HAS_TYPE
453 res = FN(PW,alloc_size)(isl_space_copy(pw->dim), pw->type, n);
454 #else
455 res = FN(PW,alloc_size)(isl_space_copy(pw->dim), n);
456 #endif
457 if (!res)
458 return FN(PW,free)(pw);
459 for (i = 0; i < pw->n; ++i)
460 res = FN(PW,add_piece)(res, isl_set_copy(pw->p[i].set),
461 FN(EL,copy)(pw->p[i].FIELD));
462 FN(PW,free)(pw);
463 return res;
464 }
465
466 static __isl_give PW *FN(PW,add_disjoint_aligned)(__isl_take PW *pw1,
467 __isl_take PW *pw2)
468 {
469 int i;
470 isl_ctx *ctx;
471
472 if (!pw1 || !pw2)
473 goto error;
474
475 if (pw1->size < pw1->n + pw2->n && pw1->n < pw2->n)
476 return FN(PW,add_disjoint_aligned)(pw2, pw1);
477
478 ctx = isl_space_get_ctx(pw1->dim);
479 #ifdef HAS_TYPE
480 if (pw1->type != pw2->type)
481 isl_die(ctx, isl_error_invalid,
482 "fold types don't match", goto error);
483 #endif
484 isl_assert(ctx, isl_space_is_equal(pw1->dim, pw2->dim), goto error);
485
486 if (FN(PW,IS_ZERO)(pw1)) {
487 FN(PW,free)(pw1);
488 return pw2;
489 }
490
491 if (FN(PW,IS_ZERO)(pw2)) {
492 FN(PW,free)(pw2);
493 return pw1;
494 }
495
496 pw1 = FN(PW,grow)(pw1, pw2->n);
497 if (!pw1)
498 goto error;
499
500 for (i = 0; i < pw2->n; ++i)
501 pw1 = FN(PW,add_piece)(pw1,
502 isl_set_copy(pw2->p[i].set),
503 FN(EL,copy)(pw2->p[i].FIELD));
504
505 FN(PW,free)(pw2);
506
507 return pw1;
508 error:
509 FN(PW,free)(pw1);
510 FN(PW,free)(pw2);
511 return NULL;
512 }
513
514 __isl_give PW *FN(PW,add_disjoint)(__isl_take PW *pw1, __isl_take PW *pw2)
515 {
516 return FN(PW,align_params_pw_pw_and)(pw1, pw2,
517 &FN(PW,add_disjoint_aligned));
518 }
519
520 /* This function is currently only used from isl_aff.c
521 */
522 static __isl_give PW *FN(PW,on_shared_domain_in)(__isl_take PW *pw1,
523 __isl_take PW *pw2, __isl_take isl_space *space,
524 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))
525 __attribute__ ((unused));
526
527 /* Apply "fn" to pairs of elements from pw1 and pw2 on shared domains.
528 * The result of "fn" (and therefore also of this function) lives in "space".
529 */
530 static __isl_give PW *FN(PW,on_shared_domain_in)(__isl_take PW *pw1,
531 __isl_take PW *pw2, __isl_take isl_space *space,
532 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))
533 {
534 int i, j, n;
535 PW *res = NULL;
536
537 if (!pw1 || !pw2)
538 goto error;
539
540 n = pw1->n * pw2->n;
541 #ifdef HAS_TYPE
542 res = FN(PW,alloc_size)(isl_space_copy(space), pw1->type, n);
543 #else
544 res = FN(PW,alloc_size)(isl_space_copy(space), n);
545 #endif
546
547 for (i = 0; i < pw1->n; ++i) {
548 for (j = 0; j < pw2->n; ++j) {
549 isl_set *common;
550 EL *res_ij;
551 int empty;
552
553 common = isl_set_intersect(
554 isl_set_copy(pw1->p[i].set),
555 isl_set_copy(pw2->p[j].set));
556 empty = isl_set_plain_is_empty(common);
557 if (empty < 0 || empty) {
558 isl_set_free(common);
559 if (empty < 0)
560 goto error;
561 continue;
562 }
563
564 res_ij = fn(FN(EL,copy)(pw1->p[i].FIELD),
565 FN(EL,copy)(pw2->p[j].FIELD));
566 res_ij = FN(EL,gist)(res_ij, isl_set_copy(common));
567
568 res = FN(PW,add_piece)(res, common, res_ij);
569 }
570 }
571
572 isl_space_free(space);
573 FN(PW,free)(pw1);
574 FN(PW,free)(pw2);
575 return res;
576 error:
577 isl_space_free(space);
578 FN(PW,free)(pw1);
579 FN(PW,free)(pw2);
580 FN(PW,free)(res);
581 return NULL;
582 }
583
584 /* This function is currently only used from isl_aff.c
585 */
586 static __isl_give PW *FN(PW,on_shared_domain)(__isl_take PW *pw1,
587 __isl_take PW *pw2,
588 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))
589 __attribute__ ((unused));
590
591 /* Apply "fn" to pairs of elements from pw1 and pw2 on shared domains.
592 * The result of "fn" is assumed to live in the same space as "pw1" and "pw2".
593 */
594 static __isl_give PW *FN(PW,on_shared_domain)(__isl_take PW *pw1,
595 __isl_take PW *pw2,
596 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))
597 {
598 isl_space *space;
599
600 if (!pw1 || !pw2)
601 goto error;
602
603 space = isl_space_copy(pw1->dim);
604 return FN(PW,on_shared_domain_in)(pw1, pw2, space, fn);
605 error:
606 FN(PW,free)(pw1);
607 FN(PW,free)(pw2);
608 return NULL;
609 }
610
611 #ifndef NO_NEG
612 __isl_give PW *FN(PW,neg)(__isl_take PW *pw)
613 {
614 int i;
615
616 if (!pw)
617 return NULL;
618
619 if (FN(PW,IS_ZERO)(pw))
620 return pw;
621
622 pw = FN(PW,cow)(pw);
623 if (!pw)
624 return NULL;
625
626 for (i = 0; i < pw->n; ++i) {
627 pw->p[i].FIELD = FN(EL,neg)(pw->p[i].FIELD);
628 if (!pw->p[i].FIELD)
629 return FN(PW,free)(pw);
630 }
631
632 return pw;
633 }
634
635 __isl_give PW *FN(PW,sub)(__isl_take PW *pw1, __isl_take PW *pw2)
636 {
637 return FN(PW,add)(pw1, FN(PW,neg)(pw2));
638 }
639 #endif
640
641 #ifndef NO_EVAL
642 __isl_give isl_val *FN(PW,eval)(__isl_take PW *pw, __isl_take isl_point *pnt)
643 {
644 int i;
645 int found = 0;
646 isl_ctx *ctx;
647 isl_space *pnt_dim = NULL;
648 isl_val *v;
649
650 if (!pw || !pnt)
651 goto error;
652 ctx = isl_point_get_ctx(pnt);
653 pnt_dim = isl_point_get_space(pnt);
654 isl_assert(ctx, isl_space_is_domain_internal(pnt_dim, pw->dim),
655 goto error);
656
657 for (i = 0; i < pw->n; ++i) {
658 found = isl_set_contains_point(pw->p[i].set, pnt);
659 if (found < 0)
660 goto error;
661 if (found)
662 break;
663 }
664 if (found)
665 v = FN(EL,eval)(FN(EL,copy)(pw->p[i].FIELD),
666 isl_point_copy(pnt));
667 else
668 v = isl_val_zero(ctx);
669 FN(PW,free)(pw);
670 isl_space_free(pnt_dim);
671 isl_point_free(pnt);
672 return v;
673 error:
674 FN(PW,free)(pw);
675 isl_space_free(pnt_dim);
676 isl_point_free(pnt);
677 return NULL;
678 }
679 #endif
680
681 __isl_give isl_set *FN(PW,domain)(__isl_take PW *pw)
682 {
683 int i;
684 isl_set *dom;
685
686 if (!pw)
687 return NULL;
688
689 dom = isl_set_empty(FN(PW,get_domain_space)(pw));
690 for (i = 0; i < pw->n; ++i)
691 dom = isl_set_union_disjoint(dom, isl_set_copy(pw->p[i].set));
692
693 FN(PW,free)(pw);
694
695 return dom;
696 }
697
698 /* Exploit the equalities in the domain of piece "i" of "pw"
699 * to simplify the associated function.
700 * If the domain of piece "i" is empty, then remove it entirely,
701 * replacing it with the final piece.
702 */
703 static int FN(PW,exploit_equalities_and_remove_if_empty)(__isl_keep PW *pw,
704 int i)
705 {
706 isl_basic_set *aff;
707 int empty = isl_set_plain_is_empty(pw->p[i].set);
708
709 if (empty < 0)
710 return -1;
711 if (empty) {
712 isl_set_free(pw->p[i].set);
713 FN(EL,free)(pw->p[i].FIELD);
714 if (i != pw->n - 1)
715 pw->p[i] = pw->p[pw->n - 1];
716 pw->n--;
717
718 return 0;
719 }
720
721 aff = isl_set_affine_hull(isl_set_copy(pw->p[i].set));
722 pw->p[i].FIELD = FN(EL,substitute_equalities)(pw->p[i].FIELD, aff);
723 if (!pw->p[i].FIELD)
724 return -1;
725
726 return 0;
727 }
728
729 /* Restrict the domain of "pw" by combining each cell
730 * with "set" through a call to "fn", where "fn" may be
731 * isl_set_intersect or isl_set_intersect_params.
732 */
733 static __isl_give PW *FN(PW,intersect_aligned)(__isl_take PW *pw,
734 __isl_take isl_set *set,
735 __isl_give isl_set *(*fn)(__isl_take isl_set *set1,
736 __isl_take isl_set *set2))
737 {
738 int i;
739
740 if (!pw || !set)
741 goto error;
742
743 if (pw->n == 0) {
744 isl_set_free(set);
745 return pw;
746 }
747
748 pw = FN(PW,cow)(pw);
749 if (!pw)
750 goto error;
751
752 for (i = pw->n - 1; i >= 0; --i) {
753 pw->p[i].set = fn(pw->p[i].set, isl_set_copy(set));
754 if (FN(PW,exploit_equalities_and_remove_if_empty)(pw, i) < 0)
755 goto error;
756 }
757
758 isl_set_free(set);
759 return pw;
760 error:
761 isl_set_free(set);
762 FN(PW,free)(pw);
763 return NULL;
764 }
765
766 static __isl_give PW *FN(PW,intersect_domain_aligned)(__isl_take PW *pw,
767 __isl_take isl_set *set)
768 {
769 return FN(PW,intersect_aligned)(pw, set, &isl_set_intersect);
770 }
771
772 __isl_give PW *FN(PW,intersect_domain)(__isl_take PW *pw,
773 __isl_take isl_set *context)
774 {
775 return FN(PW,align_params_pw_set_and)(pw, context,
776 &FN(PW,intersect_domain_aligned));
777 }
778
779 static __isl_give PW *FN(PW,intersect_params_aligned)(__isl_take PW *pw,
780 __isl_take isl_set *set)
781 {
782 return FN(PW,intersect_aligned)(pw, set, &isl_set_intersect_params);
783 }
784
785 /* Intersect the domain of "pw" with the parameter domain "context".
786 */
787 __isl_give PW *FN(PW,intersect_params)(__isl_take PW *pw,
788 __isl_take isl_set *context)
789 {
790 return FN(PW,align_params_pw_set_and)(pw, context,
791 &FN(PW,intersect_params_aligned));
792 }
793
794 static __isl_give PW *FN(PW,gist_aligned)(__isl_take PW *pw,
795 __isl_take isl_set *context,
796 __isl_give EL *(*fn_el)(__isl_take EL *el,
797 __isl_take isl_set *set),
798 __isl_give isl_set *(*fn_dom)(__isl_take isl_set *set,
799 __isl_take isl_basic_set *bset))
800 {
801 int i;
802 isl_basic_set *hull = NULL;
803
804 if (!pw || !context)
805 goto error;
806
807 if (pw->n == 0) {
808 isl_set_free(context);
809 return pw;
810 }
811
812 if (!isl_space_match(pw->dim, isl_dim_param,
813 context->dim, isl_dim_param)) {
814 pw = FN(PW,align_params)(pw, isl_set_get_space(context));
815 context = isl_set_align_params(context, FN(PW,get_space)(pw));
816 }
817
818 context = isl_set_compute_divs(context);
819 hull = isl_set_simple_hull(isl_set_copy(context));
820
821 pw = FN(PW,cow)(pw);
822 if (!pw)
823 goto error;
824
825 for (i = pw->n - 1; i >= 0; --i) {
826 isl_set *set_i;
827 int empty;
828
829 set_i = isl_set_intersect(isl_set_copy(pw->p[i].set),
830 isl_set_copy(context));
831 empty = isl_set_plain_is_empty(set_i);
832 pw->p[i].FIELD = fn_el(pw->p[i].FIELD, set_i);
833 pw->p[i].set = fn_dom(pw->p[i].set, isl_basic_set_copy(hull));
834 if (!pw->p[i].FIELD || !pw->p[i].set)
835 goto error;
836 if (empty) {
837 isl_set_free(pw->p[i].set);
838 FN(EL,free)(pw->p[i].FIELD);
839 if (i != pw->n - 1)
840 pw->p[i] = pw->p[pw->n - 1];
841 pw->n--;
842 }
843 }
844
845 isl_basic_set_free(hull);
846 isl_set_free(context);
847
848 return pw;
849 error:
850 FN(PW,free)(pw);
851 isl_basic_set_free(hull);
852 isl_set_free(context);
853 return NULL;
854 }
855
856 static __isl_give PW *FN(PW,gist_domain_aligned)(__isl_take PW *pw,
857 __isl_take isl_set *set)
858 {
859 return FN(PW,gist_aligned)(pw, set, &FN(EL,gist),
860 &isl_set_gist_basic_set);
861 }
862
863 __isl_give PW *FN(PW,gist)(__isl_take PW *pw, __isl_take isl_set *context)
864 {
865 return FN(PW,align_params_pw_set_and)(pw, context,
866 &FN(PW,gist_domain_aligned));
867 }
868
869 static __isl_give PW *FN(PW,gist_params_aligned)(__isl_take PW *pw,
870 __isl_take isl_set *set)
871 {
872 return FN(PW,gist_aligned)(pw, set, &FN(EL,gist_params),
873 &isl_set_gist_params_basic_set);
874 }
875
876 __isl_give PW *FN(PW,gist_params)(__isl_take PW *pw,
877 __isl_take isl_set *context)
878 {
879 return FN(PW,align_params_pw_set_and)(pw, context,
880 &FN(PW,gist_params_aligned));
881 }
882
883 __isl_give PW *FN(PW,coalesce)(__isl_take PW *pw)
884 {
885 int i, j;
886
887 if (!pw)
888 return NULL;
889 if (pw->n == 0)
890 return pw;
891
892 for (i = pw->n - 1; i >= 0; --i) {
893 for (j = i - 1; j >= 0; --j) {
894 if (!FN(EL,plain_is_equal)(pw->p[i].FIELD,
895 pw->p[j].FIELD))
896 continue;
897 pw->p[j].set = isl_set_union(pw->p[j].set,
898 pw->p[i].set);
899 FN(EL,free)(pw->p[i].FIELD);
900 if (i != pw->n - 1)
901 pw->p[i] = pw->p[pw->n - 1];
902 pw->n--;
903 break;
904 }
905 if (j >= 0)
906 continue;
907 pw->p[i].set = isl_set_coalesce(pw->p[i].set);
908 if (!pw->p[i].set)
909 goto error;
910 }
911
912 return pw;
913 error:
914 FN(PW,free)(pw);
915 return NULL;
916 }
917
918 isl_ctx *FN(PW,get_ctx)(__isl_keep PW *pw)
919 {
920 return pw ? isl_space_get_ctx(pw->dim) : NULL;
921 }
922
923 #ifndef NO_INVOLVES_DIMS
924 int FN(PW,involves_dims)(__isl_keep PW *pw, enum isl_dim_type type,
925 unsigned first, unsigned n)
926 {
927 int i;
928 enum isl_dim_type set_type;
929
930 if (!pw)
931 return -1;
932 if (pw->n == 0 || n == 0)
933 return 0;
934
935 set_type = type == isl_dim_in ? isl_dim_set : type;
936
937 for (i = 0; i < pw->n; ++i) {
938 int involves = FN(EL,involves_dims)(pw->p[i].FIELD,
939 type, first, n);
940 if (involves < 0 || involves)
941 return involves;
942 involves = isl_set_involves_dims(pw->p[i].set,
943 set_type, first, n);
944 if (involves < 0 || involves)
945 return involves;
946 }
947 return 0;
948 }
949 #endif
950
951 __isl_give PW *FN(PW,set_dim_name)(__isl_take PW *pw,
952 enum isl_dim_type type, unsigned pos, const char *s)
953 {
954 int i;
955 enum isl_dim_type set_type;
956
957 pw = FN(PW,cow)(pw);
958 if (!pw)
959 return NULL;
960
961 set_type = type == isl_dim_in ? isl_dim_set : type;
962
963 pw->dim = isl_space_set_dim_name(pw->dim, type, pos, s);
964 if (!pw->dim)
965 goto error;
966
967 for (i = 0; i < pw->n; ++i) {
968 pw->p[i].set = isl_set_set_dim_name(pw->p[i].set,
969 set_type, pos, s);
970 if (!pw->p[i].set)
971 goto error;
972 pw->p[i].FIELD = FN(EL,set_dim_name)(pw->p[i].FIELD, type, pos, s);
973 if (!pw->p[i].FIELD)
974 goto error;
975 }
976
977 return pw;
978 error:
979 FN(PW,free)(pw);
980 return NULL;
981 }
982
983 #ifndef NO_DROP_DIMS
984 __isl_give PW *FN(PW,drop_dims)(__isl_take PW *pw,
985 enum isl_dim_type type, unsigned first, unsigned n)
986 {
987 int i;
988 enum isl_dim_type set_type;
989
990 if (!pw)
991 return NULL;
992 if (n == 0 && !isl_space_get_tuple_name(pw->dim, type))
993 return pw;
994
995 set_type = type == isl_dim_in ? isl_dim_set : type;
996
997 pw = FN(PW,cow)(pw);
998 if (!pw)
999 return NULL;
1000 pw->dim = isl_space_drop_dims(pw->dim, type, first, n);
1001 if (!pw->dim)
1002 goto error;
1003 for (i = 0; i < pw->n; ++i) {
1004 pw->p[i].FIELD = FN(EL,drop_dims)(pw->p[i].FIELD, type, first, n);
1005 if (!pw->p[i].FIELD)
1006 goto error;
1007 if (type == isl_dim_out)
1008 continue;
1009 pw->p[i].set = isl_set_drop(pw->p[i].set, set_type, first, n);
1010 if (!pw->p[i].set)
1011 goto error;
1012 }
1013
1014 return pw;
1015 error:
1016 FN(PW,free)(pw);
1017 return NULL;
1018 }
1019
1020 /* This function is very similar to drop_dims.
1021 * The only difference is that the cells may still involve
1022 * the specified dimensions. They are removed using
1023 * isl_set_project_out instead of isl_set_drop.
1024 */
1025 __isl_give PW *FN(PW,project_out)(__isl_take PW *pw,
1026 enum isl_dim_type type, unsigned first, unsigned n)
1027 {
1028 int i;
1029 enum isl_dim_type set_type;
1030
1031 if (!pw)
1032 return NULL;
1033 if (n == 0 && !isl_space_get_tuple_name(pw->dim, type))
1034 return pw;
1035
1036 set_type = type == isl_dim_in ? isl_dim_set : type;
1037
1038 pw = FN(PW,cow)(pw);
1039 if (!pw)
1040 return NULL;
1041 pw->dim = isl_space_drop_dims(pw->dim, type, first, n);
1042 if (!pw->dim)
1043 goto error;
1044 for (i = 0; i < pw->n; ++i) {
1045 pw->p[i].set = isl_set_project_out(pw->p[i].set,
1046 set_type, first, n);
1047 if (!pw->p[i].set)
1048 goto error;
1049 pw->p[i].FIELD = FN(EL,drop_dims)(pw->p[i].FIELD, type, first, n);
1050 if (!pw->p[i].FIELD)
1051 goto error;
1052 }
1053
1054 return pw;
1055 error:
1056 FN(PW,free)(pw);
1057 return NULL;
1058 }
1059
1060 /* Project the domain of pw onto its parameter space.
1061 */
1062 __isl_give PW *FN(PW,project_domain_on_params)(__isl_take PW *pw)
1063 {
1064 isl_space *space;
1065 unsigned n;
1066
1067 n = FN(PW,dim)(pw, isl_dim_in);
1068 pw = FN(PW,project_out)(pw, isl_dim_in, 0, n);
1069 space = FN(PW,get_domain_space)(pw);
1070 space = isl_space_params(space);
1071 pw = FN(PW,reset_domain_space)(pw, space);
1072 return pw;
1073 }
1074 #endif
1075
1076 #ifndef NO_INSERT_DIMS
1077 __isl_give PW *FN(PW,insert_dims)(__isl_take PW *pw, enum isl_dim_type type,
1078 unsigned first, unsigned n)
1079 {
1080 int i;
1081 enum isl_dim_type set_type;
1082
1083 if (!pw)
1084 return NULL;
1085 if (n == 0 && !isl_space_is_named_or_nested(pw->dim, type))
1086 return pw;
1087
1088 set_type = type == isl_dim_in ? isl_dim_set : type;
1089
1090 pw = FN(PW,cow)(pw);
1091 if (!pw)
1092 return NULL;
1093
1094 pw->dim = isl_space_insert_dims(pw->dim, type, first, n);
1095 if (!pw->dim)
1096 goto error;
1097
1098 for (i = 0; i < pw->n; ++i) {
1099 pw->p[i].set = isl_set_insert_dims(pw->p[i].set,
1100 set_type, first, n);
1101 if (!pw->p[i].set)
1102 goto error;
1103 pw->p[i].FIELD = FN(EL,insert_dims)(pw->p[i].FIELD,
1104 type, first, n);
1105 if (!pw->p[i].FIELD)
1106 goto error;
1107 }
1108
1109 return pw;
1110 error:
1111 FN(PW,free)(pw);
1112 return NULL;
1113 }
1114 #endif
1115
1116 __isl_give PW *FN(PW,fix_dim)(__isl_take PW *pw,
1117 enum isl_dim_type type, unsigned pos, isl_int v)
1118 {
1119 int i;
1120
1121 if (!pw)
1122 return NULL;
1123
1124 if (type == isl_dim_in)
1125 type = isl_dim_set;
1126
1127 pw = FN(PW,cow)(pw);
1128 if (!pw)
1129 return NULL;
1130 for (i = 0; i < pw->n; ++i) {
1131 pw->p[i].set = isl_set_fix(pw->p[i].set, type, pos, v);
1132 if (FN(PW,exploit_equalities_and_remove_if_empty)(pw, i) < 0)
1133 return FN(PW,free)(pw);
1134 }
1135
1136 return pw;
1137 }
1138
1139 /* Fix the value of the variable at position "pos" of type "type" of "pw"
1140 * to be equal to "v".
1141 */
1142 __isl_give PW *FN(PW,fix_val)(__isl_take PW *pw,
1143 enum isl_dim_type type, unsigned pos, __isl_take isl_val *v)
1144 {
1145 if (!v)
1146 return FN(PW,free)(pw);
1147 if (!isl_val_is_int(v))
1148 isl_die(FN(PW,get_ctx)(pw), isl_error_invalid,
1149 "expecting integer value", goto error);
1150
1151 pw = FN(PW,fix_dim)(pw, type, pos, v->n);
1152 isl_val_free(v);
1153
1154 return pw;
1155 error:
1156 isl_val_free(v);
1157 return FN(PW,free)(pw);
1158 }
1159
1160 unsigned FN(PW,dim)(__isl_keep PW *pw, enum isl_dim_type type)
1161 {
1162 return pw ? isl_space_dim(pw->dim, type) : 0;
1163 }
1164
1165 __isl_give PW *FN(PW,split_dims)(__isl_take PW *pw,
1166 enum isl_dim_type type, unsigned first, unsigned n)
1167 {
1168 int i;
1169
1170 if (!pw)
1171 return NULL;
1172 if (n == 0)
1173 return pw;
1174
1175 if (type == isl_dim_in)
1176 type = isl_dim_set;
1177
1178 pw = FN(PW,cow)(pw);
1179 if (!pw)
1180 return NULL;
1181 if (!pw->dim)
1182 goto error;
1183 for (i = 0; i < pw->n; ++i) {
1184 pw->p[i].set = isl_set_split_dims(pw->p[i].set, type, first, n);
1185 if (!pw->p[i].set)
1186 goto error;
1187 }
1188
1189 return pw;
1190 error:
1191 FN(PW,free)(pw);
1192 return NULL;
1193 }
1194
1195 #ifndef NO_OPT
1196 /* Compute the maximal value attained by the piecewise quasipolynomial
1197 * on its domain or zero if the domain is empty.
1198 * In the worst case, the domain is scanned completely,
1199 * so the domain is assumed to be bounded.
1200 */
1201 __isl_give isl_val *FN(PW,opt)(__isl_take PW *pw, int max)
1202 {
1203 int i;
1204 isl_val *opt;
1205
1206 if (!pw)
1207 return NULL;
1208
1209 if (pw->n == 0) {
1210 opt = isl_val_zero(FN(PW,get_ctx)(pw));
1211 FN(PW,free)(pw);
1212 return opt;
1213 }
1214
1215 opt = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[0].FIELD),
1216 isl_set_copy(pw->p[0].set), max);
1217 for (i = 1; i < pw->n; ++i) {
1218 isl_val *opt_i;
1219 opt_i = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[i].FIELD),
1220 isl_set_copy(pw->p[i].set), max);
1221 if (max)
1222 opt = isl_val_max(opt, opt_i);
1223 else
1224 opt = isl_val_min(opt, opt_i);
1225 }
1226
1227 FN(PW,free)(pw);
1228 return opt;
1229 }
1230
1231 __isl_give isl_val *FN(PW,max)(__isl_take PW *pw)
1232 {
1233 return FN(PW,opt)(pw, 1);
1234 }
1235
1236 __isl_give isl_val *FN(PW,min)(__isl_take PW *pw)
1237 {
1238 return FN(PW,opt)(pw, 0);
1239 }
1240 #endif
1241
1242 __isl_give isl_space *FN(PW,get_space)(__isl_keep PW *pw)
1243 {
1244 return pw ? isl_space_copy(pw->dim) : NULL;
1245 }
1246
1247 __isl_give isl_space *FN(PW,get_domain_space)(__isl_keep PW *pw)
1248 {
1249 return pw ? isl_space_domain(isl_space_copy(pw->dim)) : NULL;
1250 }
1251
1252 #ifndef NO_RESET_DIM
1253 /* Reset the space of "pw". Since we don't know if the elements
1254 * represent the spaces themselves or their domains, we pass along
1255 * both when we call their reset_space_and_domain.
1256 */
1257 static __isl_give PW *FN(PW,reset_space_and_domain)(__isl_take PW *pw,
1258 __isl_take isl_space *space, __isl_take isl_space *domain)
1259 {
1260 int i;
1261
1262 pw = FN(PW,cow)(pw);
1263 if (!pw || !space || !domain)
1264 goto error;
1265
1266 for (i = 0; i < pw->n; ++i) {
1267 pw->p[i].set = isl_set_reset_space(pw->p[i].set,
1268 isl_space_copy(domain));
1269 if (!pw->p[i].set)
1270 goto error;
1271 pw->p[i].FIELD = FN(EL,reset_space_and_domain)(pw->p[i].FIELD,
1272 isl_space_copy(space), isl_space_copy(domain));
1273 if (!pw->p[i].FIELD)
1274 goto error;
1275 }
1276
1277 isl_space_free(domain);
1278
1279 isl_space_free(pw->dim);
1280 pw->dim = space;
1281
1282 return pw;
1283 error:
1284 isl_space_free(domain);
1285 isl_space_free(space);
1286 FN(PW,free)(pw);
1287 return NULL;
1288 }
1289
1290 __isl_give PW *FN(PW,reset_domain_space)(__isl_take PW *pw,
1291 __isl_take isl_space *domain)
1292 {
1293 isl_space *space;
1294
1295 space = isl_space_extend_domain_with_range(isl_space_copy(domain),
1296 FN(PW,get_space)(pw));
1297 return FN(PW,reset_space_and_domain)(pw, space, domain);
1298 }
1299
1300 __isl_give PW *FN(PW,reset_space)(__isl_take PW *pw, __isl_take isl_space *dim)
1301 {
1302 isl_space *domain;
1303
1304 domain = isl_space_domain(isl_space_copy(dim));
1305 return FN(PW,reset_space_and_domain)(pw, dim, domain);
1306 }
1307
1308 __isl_give PW *FN(PW,set_tuple_id)(__isl_keep PW *pw, enum isl_dim_type type,
1309 __isl_take isl_id *id)
1310 {
1311 isl_space *space;
1312
1313 pw = FN(PW,cow)(pw);
1314 if (!pw)
1315 return isl_id_free(id);
1316
1317 space = FN(PW,get_space)(pw);
1318 space = isl_space_set_tuple_id(space, type, id);
1319
1320 return FN(PW,reset_space)(pw, space);
1321 }
1322
1323 __isl_give PW *FN(PW,set_dim_id)(__isl_take PW *pw,
1324 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
1325 {
1326 pw = FN(PW,cow)(pw);
1327 if (!pw)
1328 return isl_id_free(id);
1329 pw->dim = isl_space_set_dim_id(pw->dim, type, pos, id);
1330 return FN(PW,reset_space)(pw, isl_space_copy(pw->dim));
1331 }
1332 #endif
1333
1334 int FN(PW,has_equal_space)(__isl_keep PW *pw1, __isl_keep PW *pw2)
1335 {
1336 if (!pw1 || !pw2)
1337 return -1;
1338
1339 return isl_space_is_equal(pw1->dim, pw2->dim);
1340 }
1341
1342 #ifndef NO_MORPH
1343 __isl_give PW *FN(PW,morph_domain)(__isl_take PW *pw,
1344 __isl_take isl_morph *morph)
1345 {
1346 int i;
1347 isl_ctx *ctx;
1348
1349 if (!pw || !morph)
1350 goto error;
1351
1352 ctx = isl_space_get_ctx(pw->dim);
1353 isl_assert(ctx, isl_space_is_domain_internal(morph->dom->dim, pw->dim),
1354 goto error);
1355
1356 pw = FN(PW,cow)(pw);
1357 if (!pw)
1358 goto error;
1359 pw->dim = isl_space_extend_domain_with_range(
1360 isl_space_copy(morph->ran->dim), pw->dim);
1361 if (!pw->dim)
1362 goto error;
1363
1364 for (i = 0; i < pw->n; ++i) {
1365 pw->p[i].set = isl_morph_set(isl_morph_copy(morph), pw->p[i].set);
1366 if (!pw->p[i].set)
1367 goto error;
1368 pw->p[i].FIELD = FN(EL,morph_domain)(pw->p[i].FIELD,
1369 isl_morph_copy(morph));
1370 if (!pw->p[i].FIELD)
1371 goto error;
1372 }
1373
1374 isl_morph_free(morph);
1375
1376 return pw;
1377 error:
1378 FN(PW,free)(pw);
1379 isl_morph_free(morph);
1380 return NULL;
1381 }
1382 #endif
1383
1384 int FN(PW,n_piece)(__isl_keep PW *pw)
1385 {
1386 return pw ? pw->n : 0;
1387 }
1388
1389 int FN(PW,foreach_piece)(__isl_keep PW *pw,
1390 int (*fn)(__isl_take isl_set *set, __isl_take EL *el, void *user),
1391 void *user)
1392 {
1393 int i;
1394
1395 if (!pw)
1396 return -1;
1397
1398 for (i = 0; i < pw->n; ++i)
1399 if (fn(isl_set_copy(pw->p[i].set),
1400 FN(EL,copy)(pw->p[i].FIELD), user) < 0)
1401 return -1;
1402
1403 return 0;
1404 }
1405
1406 #ifndef NO_LIFT
1407 static int any_divs(__isl_keep isl_set *set)
1408 {
1409 int i;
1410
1411 if (!set)
1412 return -1;
1413
1414 for (i = 0; i < set->n; ++i)
1415 if (set->p[i]->n_div > 0)
1416 return 1;
1417
1418 return 0;
1419 }
1420
1421 static int foreach_lifted_subset(__isl_take isl_set *set, __isl_take EL *el,
1422 int (*fn)(__isl_take isl_set *set, __isl_take EL *el,
1423 void *user), void *user)
1424 {
1425 int i;
1426
1427 if (!set || !el)
1428 goto error;
1429
1430 for (i = 0; i < set->n; ++i) {
1431 isl_set *lift;
1432 EL *copy;
1433
1434 lift = isl_set_from_basic_set(isl_basic_set_copy(set->p[i]));
1435 lift = isl_set_lift(lift);
1436
1437 copy = FN(EL,copy)(el);
1438 copy = FN(EL,lift)(copy, isl_set_get_space(lift));
1439
1440 if (fn(lift, copy, user) < 0)
1441 goto error;
1442 }
1443
1444 isl_set_free(set);
1445 FN(EL,free)(el);
1446
1447 return 0;
1448 error:
1449 isl_set_free(set);
1450 FN(EL,free)(el);
1451 return -1;
1452 }
1453
1454 int FN(PW,foreach_lifted_piece)(__isl_keep PW *pw,
1455 int (*fn)(__isl_take isl_set *set, __isl_take EL *el,
1456 void *user), void *user)
1457 {
1458 int i;
1459
1460 if (!pw)
1461 return -1;
1462
1463 for (i = 0; i < pw->n; ++i) {
1464 isl_set *set;
1465 EL *el;
1466
1467 set = isl_set_copy(pw->p[i].set);
1468 el = FN(EL,copy)(pw->p[i].FIELD);
1469 if (!any_divs(set)) {
1470 if (fn(set, el, user) < 0)
1471 return -1;
1472 continue;
1473 }
1474 if (foreach_lifted_subset(set, el, fn, user) < 0)
1475 return -1;
1476 }
1477
1478 return 0;
1479 }
1480 #endif
1481
1482 #ifndef NO_MOVE_DIMS
1483 __isl_give PW *FN(PW,move_dims)(__isl_take PW *pw,
1484 enum isl_dim_type dst_type, unsigned dst_pos,
1485 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1486 {
1487 int i;
1488
1489 pw = FN(PW,cow)(pw);
1490 if (!pw)
1491 return NULL;
1492
1493 pw->dim = isl_space_move_dims(pw->dim, dst_type, dst_pos, src_type, src_pos, n);
1494 if (!pw->dim)
1495 goto error;
1496
1497 for (i = 0; i < pw->n; ++i) {
1498 pw->p[i].FIELD = FN(EL,move_dims)(pw->p[i].FIELD,
1499 dst_type, dst_pos, src_type, src_pos, n);
1500 if (!pw->p[i].FIELD)
1501 goto error;
1502 }
1503
1504 if (dst_type == isl_dim_in)
1505 dst_type = isl_dim_set;
1506 if (src_type == isl_dim_in)
1507 src_type = isl_dim_set;
1508
1509 for (i = 0; i < pw->n; ++i) {
1510 pw->p[i].set = isl_set_move_dims(pw->p[i].set,
1511 dst_type, dst_pos,
1512 src_type, src_pos, n);
1513 if (!pw->p[i].set)
1514 goto error;
1515 }
1516
1517 return pw;
1518 error:
1519 FN(PW,free)(pw);
1520 return NULL;
1521 }
1522 #endif
1523
1524 __isl_give PW *FN(PW,mul_isl_int)(__isl_take PW *pw, isl_int v)
1525 {
1526 int i;
1527
1528 if (isl_int_is_one(v))
1529 return pw;
1530 if (pw && DEFAULT_IS_ZERO && isl_int_is_zero(v)) {
1531 PW *zero;
1532 isl_space *dim = FN(PW,get_space)(pw);
1533 #ifdef HAS_TYPE
1534 zero = FN(PW,ZERO)(dim, pw->type);
1535 #else
1536 zero = FN(PW,ZERO)(dim);
1537 #endif
1538 FN(PW,free)(pw);
1539 return zero;
1540 }
1541 pw = FN(PW,cow)(pw);
1542 if (!pw)
1543 return NULL;
1544 if (pw->n == 0)
1545 return pw;
1546
1547 #ifdef HAS_TYPE
1548 if (isl_int_is_neg(v))
1549 pw->type = isl_fold_type_negate(pw->type);
1550 #endif
1551 for (i = 0; i < pw->n; ++i) {
1552 pw->p[i].FIELD = FN(EL,scale)(pw->p[i].FIELD, v);
1553 if (!pw->p[i].FIELD)
1554 goto error;
1555 }
1556
1557 return pw;
1558 error:
1559 FN(PW,free)(pw);
1560 return NULL;
1561 }
1562
1563 /* Multiply the pieces of "pw" by "v" and return the result.
1564 */
1565 __isl_give PW *FN(PW,scale_val)(__isl_take PW *pw, __isl_take isl_val *v)
1566 {
1567 int i;
1568
1569 if (!pw || !v)
1570 goto error;
1571
1572 if (isl_val_is_one(v)) {
1573 isl_val_free(v);
1574 return pw;
1575 }
1576 if (pw && DEFAULT_IS_ZERO && isl_val_is_zero(v)) {
1577 PW *zero;
1578 isl_space *space = FN(PW,get_space)(pw);
1579 #ifdef HAS_TYPE
1580 zero = FN(PW,ZERO)(space, pw->type);
1581 #else
1582 zero = FN(PW,ZERO)(space);
1583 #endif
1584 FN(PW,free)(pw);
1585 isl_val_free(v);
1586 return zero;
1587 }
1588 if (pw->n == 0) {
1589 isl_val_free(v);
1590 return pw;
1591 }
1592 pw = FN(PW,cow)(pw);
1593 if (!pw)
1594 goto error;
1595
1596 #ifdef HAS_TYPE
1597 if (isl_val_is_neg(v))
1598 pw->type = isl_fold_type_negate(pw->type);
1599 #endif
1600 for (i = 0; i < pw->n; ++i) {
1601 pw->p[i].FIELD = FN(EL,scale_val)(pw->p[i].FIELD,
1602 isl_val_copy(v));
1603 if (!pw->p[i].FIELD)
1604 goto error;
1605 }
1606
1607 isl_val_free(v);
1608 return pw;
1609 error:
1610 isl_val_free(v);
1611 FN(PW,free)(pw);
1612 return NULL;
1613 }
1614
1615 __isl_give PW *FN(PW,scale)(__isl_take PW *pw, isl_int v)
1616 {
1617 return FN(PW,mul_isl_int)(pw, v);
1618 }
1619
1620 static int FN(PW,qsort_set_cmp)(const void *p1, const void *p2)
1621 {
1622 isl_set *set1 = *(isl_set * const *)p1;
1623 isl_set *set2 = *(isl_set * const *)p2;
1624
1625 return isl_set_plain_cmp(set1, set2);
1626 }
1627
1628 /* We normalize in place, but if anything goes wrong we need
1629 * to return NULL, so we need to make sure we don't change the
1630 * meaning of any possible other copies of map.
1631 */
1632 __isl_give PW *FN(PW,normalize)(__isl_take PW *pw)
1633 {
1634 int i, j;
1635 isl_set *set;
1636
1637 if (!pw)
1638 return NULL;
1639 for (i = 0; i < pw->n; ++i) {
1640 set = isl_set_normalize(isl_set_copy(pw->p[i].set));
1641 if (!set)
1642 return FN(PW,free)(pw);
1643 isl_set_free(pw->p[i].set);
1644 pw->p[i].set = set;
1645 }
1646 qsort(pw->p, pw->n, sizeof(pw->p[0]), &FN(PW,qsort_set_cmp));
1647 for (i = pw->n - 1; i >= 1; --i) {
1648 if (!isl_set_plain_is_equal(pw->p[i - 1].set, pw->p[i].set))
1649 continue;
1650 if (!FN(EL,plain_is_equal)(pw->p[i - 1].FIELD, pw->p[i].FIELD))
1651 continue;
1652 set = isl_set_union(isl_set_copy(pw->p[i - 1].set),
1653 isl_set_copy(pw->p[i].set));
1654 if (!set)
1655 return FN(PW,free)(pw);
1656 isl_set_free(pw->p[i].set);
1657 FN(EL,free)(pw->p[i].FIELD);
1658 isl_set_free(pw->p[i - 1].set);
1659 pw->p[i - 1].set = set;
1660 for (j = i + 1; j < pw->n; ++j)
1661 pw->p[j - 1] = pw->p[j];
1662 pw->n--;
1663 }
1664
1665 return pw;
1666 }
1667
1668 /* Is pw1 obviously equal to pw2?
1669 * That is, do they have obviously identical cells and obviously identical
1670 * elements on each cell?
1671 */
1672 int FN(PW,plain_is_equal)(__isl_keep PW *pw1, __isl_keep PW *pw2)
1673 {
1674 int i;
1675 int equal;
1676
1677 if (!pw1 || !pw2)
1678 return -1;
1679
1680 if (pw1 == pw2)
1681 return 1;
1682 if (!isl_space_is_equal(pw1->dim, pw2->dim))
1683 return 0;
1684
1685 pw1 = FN(PW,copy)(pw1);
1686 pw2 = FN(PW,copy)(pw2);
1687 pw1 = FN(PW,normalize)(pw1);
1688 pw2 = FN(PW,normalize)(pw2);
1689 if (!pw1 || !pw2)
1690 goto error;
1691
1692 equal = pw1->n == pw2->n;
1693 for (i = 0; equal && i < pw1->n; ++i) {
1694 equal = isl_set_plain_is_equal(pw1->p[i].set, pw2->p[i].set);
1695 if (equal < 0)
1696 goto error;
1697 if (!equal)
1698 break;
1699 equal = FN(EL,plain_is_equal)(pw1->p[i].FIELD, pw2->p[i].FIELD);
1700 if (equal < 0)
1701 goto error;
1702 }
1703
1704 FN(PW,free)(pw1);
1705 FN(PW,free)(pw2);
1706 return equal;
1707 error:
1708 FN(PW,free)(pw1);
1709 FN(PW,free)(pw2);
1710 return -1;
1711 }
1712
1713 #ifndef NO_PULLBACK
1714 static __isl_give PW *FN(PW,align_params_pw_multi_aff_and)(__isl_take PW *pw,
1715 __isl_take isl_multi_aff *ma,
1716 __isl_give PW *(*fn)(__isl_take PW *pw, __isl_take isl_multi_aff *ma))
1717 {
1718 isl_ctx *ctx;
1719 isl_space *ma_space;
1720
1721 ma_space = isl_multi_aff_get_space(ma);
1722 if (!pw || !ma || !ma_space)
1723 goto error;
1724 if (isl_space_match(pw->dim, isl_dim_param, ma_space, isl_dim_param)) {
1725 isl_space_free(ma_space);
1726 return fn(pw, ma);
1727 }
1728 ctx = FN(PW,get_ctx)(pw);
1729 if (!isl_space_has_named_params(pw->dim) ||
1730 !isl_space_has_named_params(ma_space))
1731 isl_die(ctx, isl_error_invalid,
1732 "unaligned unnamed parameters", goto error);
1733 pw = FN(PW,align_params)(pw, ma_space);
1734 ma = isl_multi_aff_align_params(ma, FN(PW,get_space)(pw));
1735 return fn(pw, ma);
1736 error:
1737 isl_space_free(ma_space);
1738 FN(PW,free)(pw);
1739 isl_multi_aff_free(ma);
1740 return NULL;
1741 }
1742
1743 static __isl_give PW *FN(PW,align_params_pw_pw_multi_aff_and)(__isl_take PW *pw,
1744 __isl_take isl_pw_multi_aff *pma,
1745 __isl_give PW *(*fn)(__isl_take PW *pw,
1746 __isl_take isl_pw_multi_aff *ma))
1747 {
1748 isl_ctx *ctx;
1749 isl_space *pma_space;
1750
1751 pma_space = isl_pw_multi_aff_get_space(pma);
1752 if (!pw || !pma || !pma_space)
1753 goto error;
1754 if (isl_space_match(pw->dim, isl_dim_param, pma_space, isl_dim_param)) {
1755 isl_space_free(pma_space);
1756 return fn(pw, pma);
1757 }
1758 ctx = FN(PW,get_ctx)(pw);
1759 if (!isl_space_has_named_params(pw->dim) ||
1760 !isl_space_has_named_params(pma_space))
1761 isl_die(ctx, isl_error_invalid,
1762 "unaligned unnamed parameters", goto error);
1763 pw = FN(PW,align_params)(pw, pma_space);
1764 pma = isl_pw_multi_aff_align_params(pma, FN(PW,get_space)(pw));
1765 return fn(pw, pma);
1766 error:
1767 isl_space_free(pma_space);
1768 FN(PW,free)(pw);
1769 isl_pw_multi_aff_free(pma);
1770 return NULL;
1771 }
1772
1773 /* Compute the pullback of "pw" by the function represented by "ma".
1774 * In other words, plug in "ma" in "pw".
1775 */
1776 static __isl_give PW *FN(PW,pullback_multi_aff_aligned)(__isl_take PW *pw,
1777 __isl_take isl_multi_aff *ma)
1778 {
1779 int i;
1780 isl_space *space = NULL;
1781
1782 ma = isl_multi_aff_align_divs(ma);
1783 pw = FN(PW,cow)(pw);
1784 if (!pw || !ma)
1785 goto error;
1786
1787 space = isl_space_join(isl_multi_aff_get_space(ma),
1788 FN(PW,get_space)(pw));
1789
1790 for (i = 0; i < pw->n; ++i) {
1791 pw->p[i].set = isl_set_preimage_multi_aff(pw->p[i].set,
1792 isl_multi_aff_copy(ma));
1793 if (!pw->p[i].set)
1794 goto error;
1795 pw->p[i].FIELD = FN(EL,pullback_multi_aff)(pw->p[i].FIELD,
1796 isl_multi_aff_copy(ma));
1797 if (!pw->p[i].FIELD)
1798 goto error;
1799 }
1800
1801 pw = FN(PW,reset_space)(pw, space);
1802 isl_multi_aff_free(ma);
1803 return pw;
1804 error:
1805 isl_space_free(space);
1806 isl_multi_aff_free(ma);
1807 FN(PW,free)(pw);
1808 return NULL;
1809 }
1810
1811 __isl_give PW *FN(PW,pullback_multi_aff)(__isl_take PW *pw,
1812 __isl_take isl_multi_aff *ma)
1813 {
1814 return FN(PW,align_params_pw_multi_aff_and)(pw, ma,
1815 &FN(PW,pullback_multi_aff_aligned));
1816 }
1817
1818 /* Compute the pullback of "pw" by the function represented by "pma".
1819 * In other words, plug in "pma" in "pw".
1820 */
1821 static __isl_give PW *FN(PW,pullback_pw_multi_aff_aligned)(__isl_take PW *pw,
1822 __isl_take isl_pw_multi_aff *pma)
1823 {
1824 int i;
1825 PW *res;
1826
1827 if (!pma)
1828 goto error;
1829
1830 if (pma->n == 0) {
1831 isl_pw_multi_aff_free(pma);
1832 res = FN(PW,empty)(FN(PW,get_space)(pw));
1833 FN(PW,free)(pw);
1834 return res;
1835 }
1836
1837 res = FN(PW,pullback_multi_aff)(FN(PW,copy)(pw),
1838 isl_multi_aff_copy(pma->p[0].maff));
1839 res = FN(PW,intersect_domain)(res, isl_set_copy(pma->p[0].set));
1840
1841 for (i = 1; i < pma->n; ++i) {
1842 PW *res_i;
1843
1844 res_i = FN(PW,pullback_multi_aff)(FN(PW,copy)(pw),
1845 isl_multi_aff_copy(pma->p[i].maff));
1846 res_i = FN(PW,intersect_domain)(res_i,
1847 isl_set_copy(pma->p[i].set));
1848 res = FN(PW,add_disjoint)(res, res_i);
1849 }
1850
1851 isl_pw_multi_aff_free(pma);
1852 FN(PW,free)(pw);
1853 return res;
1854 error:
1855 isl_pw_multi_aff_free(pma);
1856 FN(PW,free)(pw);
1857 return NULL;
1858 }
1859
1860 __isl_give PW *FN(PW,pullback_pw_multi_aff)(__isl_take PW *pw,
1861 __isl_take isl_pw_multi_aff *pma)
1862 {
1863 return FN(PW,align_params_pw_pw_multi_aff_and)(pw, pma,
1864 &FN(PW,pullback_pw_multi_aff_aligned));
1865 }
1866 #endif
Integer set library