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