?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_ast_build_expr.c: isl_ast_expr_add_term: allow stealing from constant term
[isl.git] / isl_pw_templ.c
blob223557f9beb3215cfdaad394a8829bcaf2ced3eb
1 /*
2 * Copyright 2010-2011 INRIA Saclay
3 * Copyright 2011 Sven Verdoolaege
4 * Copyright 2012-2014 Ecole Normale Superieure
5 *
6 * Use of this software is governed by the MIT license
7 *
8 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
9 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10 * 91893 Orsay, France
11 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
12 */
13
14 #include <isl/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 __isl_null PW *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 /* Return the parameter domain of "pw".
695 */
696 __isl_give isl_set *FN(PW,params)(__isl_take PW *pw)
697 {
698 return isl_set_params(FN(PW,domain)(pw));
699 }
700
701 __isl_give isl_set *FN(PW,domain)(__isl_take PW *pw)
702 {
703 int i;
704 isl_set *dom;
705
706 if (!pw)
707 return NULL;
708
709 dom = isl_set_empty(FN(PW,get_domain_space)(pw));
710 for (i = 0; i < pw->n; ++i)
711 dom = isl_set_union_disjoint(dom, isl_set_copy(pw->p[i].set));
712
713 FN(PW,free)(pw);
714
715 return dom;
716 }
717
718 /* Exploit the equalities in the domain of piece "i" of "pw"
719 * to simplify the associated function.
720 * If the domain of piece "i" is empty, then remove it entirely,
721 * replacing it with the final piece.
722 */
723 static int FN(PW,exploit_equalities_and_remove_if_empty)(__isl_keep PW *pw,
724 int i)
725 {
726 isl_basic_set *aff;
727 int empty = isl_set_plain_is_empty(pw->p[i].set);
728
729 if (empty < 0)
730 return -1;
731 if (empty) {
732 isl_set_free(pw->p[i].set);
733 FN(EL,free)(pw->p[i].FIELD);
734 if (i != pw->n - 1)
735 pw->p[i] = pw->p[pw->n - 1];
736 pw->n--;
737
738 return 0;
739 }
740
741 aff = isl_set_affine_hull(isl_set_copy(pw->p[i].set));
742 pw->p[i].FIELD = FN(EL,substitute_equalities)(pw->p[i].FIELD, aff);
743 if (!pw->p[i].FIELD)
744 return -1;
745
746 return 0;
747 }
748
749 /* Convert a piecewise expression defined over a parameter domain
750 * into one that is defined over a zero-dimensional set.
751 */
752 __isl_give PW *FN(PW,from_range)(__isl_take PW *pw)
753 {
754 isl_space *space;
755
756 if (!pw)
757 return NULL;
758 if (!isl_space_is_set(pw->dim))
759 isl_die(FN(PW,get_ctx)(pw), isl_error_invalid,
760 "not living in a set space", return FN(PW,free)(pw));
761
762 space = FN(PW,get_space)(pw);
763 space = isl_space_from_range(space);
764 pw = FN(PW,reset_space)(pw, space);
765
766 return pw;
767 }
768
769 /* Fix the value of the given parameter or domain dimension of "pw"
770 * to be equal to "value".
771 */
772 __isl_give PW *FN(PW,fix_si)(__isl_take PW *pw, enum isl_dim_type type,
773 unsigned pos, int value)
774 {
775 int i;
776
777 if (!pw)
778 return NULL;
779
780 if (type == isl_dim_out)
781 isl_die(FN(PW,get_ctx)(pw), isl_error_invalid,
782 "cannot fix output dimension", return FN(PW,free)(pw));
783
784 if (pw->n == 0)
785 return pw;
786
787 if (type == isl_dim_in)
788 type = isl_dim_set;
789
790 pw = FN(PW,cow)(pw);
791 if (!pw)
792 return FN(PW,free)(pw);
793
794 for (i = pw->n - 1; i >= 0; --i) {
795 pw->p[i].set = isl_set_fix_si(pw->p[i].set, type, pos, value);
796 if (FN(PW,exploit_equalities_and_remove_if_empty)(pw, i) < 0)
797 return FN(PW,free)(pw);
798 }
799
800 return pw;
801 }
802
803 /* Restrict the domain of "pw" by combining each cell
804 * with "set" through a call to "fn", where "fn" may be
805 * isl_set_intersect, isl_set_intersect_params or isl_set_subtract.
806 */
807 static __isl_give PW *FN(PW,restrict_domain_aligned)(__isl_take PW *pw,
808 __isl_take isl_set *set,
809 __isl_give isl_set *(*fn)(__isl_take isl_set *set1,
810 __isl_take isl_set *set2))
811 {
812 int i;
813
814 if (!pw || !set)
815 goto error;
816
817 if (pw->n == 0) {
818 isl_set_free(set);
819 return pw;
820 }
821
822 pw = FN(PW,cow)(pw);
823 if (!pw)
824 goto error;
825
826 for (i = pw->n - 1; i >= 0; --i) {
827 pw->p[i].set = fn(pw->p[i].set, isl_set_copy(set));
828 if (FN(PW,exploit_equalities_and_remove_if_empty)(pw, i) < 0)
829 goto error;
830 }
831
832 isl_set_free(set);
833 return pw;
834 error:
835 isl_set_free(set);
836 FN(PW,free)(pw);
837 return NULL;
838 }
839
840 static __isl_give PW *FN(PW,intersect_domain_aligned)(__isl_take PW *pw,
841 __isl_take isl_set *set)
842 {
843 return FN(PW,restrict_domain_aligned)(pw, set, &isl_set_intersect);
844 }
845
846 __isl_give PW *FN(PW,intersect_domain)(__isl_take PW *pw,
847 __isl_take isl_set *context)
848 {
849 return FN(PW,align_params_pw_set_and)(pw, context,
850 &FN(PW,intersect_domain_aligned));
851 }
852
853 static __isl_give PW *FN(PW,intersect_params_aligned)(__isl_take PW *pw,
854 __isl_take isl_set *set)
855 {
856 return FN(PW,restrict_domain_aligned)(pw, set,
857 &isl_set_intersect_params);
858 }
859
860 /* Intersect the domain of "pw" with the parameter domain "context".
861 */
862 __isl_give PW *FN(PW,intersect_params)(__isl_take PW *pw,
863 __isl_take isl_set *context)
864 {
865 return FN(PW,align_params_pw_set_and)(pw, context,
866 &FN(PW,intersect_params_aligned));
867 }
868
869 /* Subtract "domain' from the domain of "pw", assuming their
870 * parameters have been aligned.
871 */
872 static __isl_give PW *FN(PW,subtract_domain_aligned)(__isl_take PW *pw,
873 __isl_take isl_set *domain)
874 {
875 return FN(PW,restrict_domain_aligned)(pw, domain, &isl_set_subtract);
876 }
877
878 /* Subtract "domain' from the domain of "pw".
879 */
880 __isl_give PW *FN(PW,subtract_domain)(__isl_take PW *pw,
881 __isl_take isl_set *domain)
882 {
883 return FN(PW,align_params_pw_set_and)(pw, domain,
884 &FN(PW,subtract_domain_aligned));
885 }
886
887 /* Compute the gist of "pw" with respect to the domain constraints
888 * of "context" for the case where the domain of the last element
889 * of "pw" is equal to "context".
890 * Call "fn_el" to compute the gist of this element, replace
891 * its domain by the universe and drop all other elements
892 * as their domains are necessarily disjoint from "context".
893 */
894 static __isl_give PW *FN(PW,gist_last)(__isl_take PW *pw,
895 __isl_take isl_set *context,
896 __isl_give EL *(*fn_el)(__isl_take EL *el, __isl_take isl_set *set))
897 {
898 int i;
899 isl_space *space;
900
901 for (i = 0; i < pw->n - 1; ++i) {
902 isl_set_free(pw->p[i].set);
903 FN(EL,free)(pw->p[i].FIELD);
904 }
905 pw->p[0].FIELD = pw->p[pw->n - 1].FIELD;
906 pw->p[0].set = pw->p[pw->n - 1].set;
907 pw->n = 1;
908
909 space = isl_set_get_space(context);
910 pw->p[0].FIELD = fn_el(pw->p[0].FIELD, context);
911 context = isl_set_universe(space);
912 isl_set_free(pw->p[0].set);
913 pw->p[0].set = context;
914
915 if (!pw->p[0].FIELD || !pw->p[0].set)
916 return FN(PW,free)(pw);
917
918 return pw;
919 }
920
921 /* Compute the gist of "pw" with respect to the domain constraints
922 * of "context". Call "fn_el" to compute the gist of the elements
923 * and "fn_dom" to compute the gist of the domains.
924 *
925 * If the piecewise expression is empty or the context is the universe,
926 * then nothing can be simplified.
927 */
928 static __isl_give PW *FN(PW,gist_aligned)(__isl_take PW *pw,
929 __isl_take isl_set *context,
930 __isl_give EL *(*fn_el)(__isl_take EL *el,
931 __isl_take isl_set *set),
932 __isl_give isl_set *(*fn_dom)(__isl_take isl_set *set,
933 __isl_take isl_basic_set *bset))
934 {
935 int i;
936 int is_universe;
937 isl_basic_set *hull = NULL;
938
939 if (!pw || !context)
940 goto error;
941
942 if (pw->n == 0) {
943 isl_set_free(context);
944 return pw;
945 }
946
947 is_universe = isl_set_plain_is_universe(context);
948 if (is_universe < 0)
949 goto error;
950 if (is_universe) {
951 isl_set_free(context);
952 return pw;
953 }
954
955 if (!isl_space_match(pw->dim, isl_dim_param,
956 context->dim, isl_dim_param)) {
957 pw = FN(PW,align_params)(pw, isl_set_get_space(context));
958 context = isl_set_align_params(context, FN(PW,get_space)(pw));
959 }
960
961 pw = FN(PW,cow)(pw);
962 if (!pw)
963 goto error;
964
965 if (pw->n == 1) {
966 int equal;
967
968 equal = isl_set_plain_is_equal(pw->p[0].set, context);
969 if (equal < 0)
970 goto error;
971 if (equal)
972 return FN(PW,gist_last)(pw, context, fn_el);
973 }
974
975 context = isl_set_compute_divs(context);
976 hull = isl_set_simple_hull(isl_set_copy(context));
977
978 for (i = pw->n - 1; i >= 0; --i) {
979 isl_set *set_i;
980 int empty;
981
982 if (i == pw->n - 1) {
983 int equal;
984 equal = isl_set_plain_is_equal(pw->p[i].set, context);
985 if (equal < 0)
986 goto error;
987 if (equal) {
988 isl_basic_set_free(hull);
989 return FN(PW,gist_last)(pw, context, fn_el);
990 }
991 }
992 set_i = isl_set_intersect(isl_set_copy(pw->p[i].set),
993 isl_set_copy(context));
994 empty = isl_set_plain_is_empty(set_i);
995 pw->p[i].FIELD = fn_el(pw->p[i].FIELD, set_i);
996 pw->p[i].set = fn_dom(pw->p[i].set, isl_basic_set_copy(hull));
997 if (empty < 0 || !pw->p[i].FIELD || !pw->p[i].set)
998 goto error;
999 if (empty) {
1000 isl_set_free(pw->p[i].set);
1001 FN(EL,free)(pw->p[i].FIELD);
1002 if (i != pw->n - 1)
1003 pw->p[i] = pw->p[pw->n - 1];
1004 pw->n--;
1005 }
1006 }
1007
1008 isl_basic_set_free(hull);
1009 isl_set_free(context);
1010
1011 return pw;
1012 error:
1013 FN(PW,free)(pw);
1014 isl_basic_set_free(hull);
1015 isl_set_free(context);
1016 return NULL;
1017 }
1018
1019 static __isl_give PW *FN(PW,gist_domain_aligned)(__isl_take PW *pw,
1020 __isl_take isl_set *set)
1021 {
1022 return FN(PW,gist_aligned)(pw, set, &FN(EL,gist),
1023 &isl_set_gist_basic_set);
1024 }
1025
1026 __isl_give PW *FN(PW,gist)(__isl_take PW *pw, __isl_take isl_set *context)
1027 {
1028 return FN(PW,align_params_pw_set_and)(pw, context,
1029 &FN(PW,gist_domain_aligned));
1030 }
1031
1032 static __isl_give PW *FN(PW,gist_params_aligned)(__isl_take PW *pw,
1033 __isl_take isl_set *set)
1034 {
1035 return FN(PW,gist_aligned)(pw, set, &FN(EL,gist_params),
1036 &isl_set_gist_params_basic_set);
1037 }
1038
1039 __isl_give PW *FN(PW,gist_params)(__isl_take PW *pw,
1040 __isl_take isl_set *context)
1041 {
1042 return FN(PW,align_params_pw_set_and)(pw, context,
1043 &FN(PW,gist_params_aligned));
1044 }
1045
1046 __isl_give PW *FN(PW,coalesce)(__isl_take PW *pw)
1047 {
1048 int i, j;
1049
1050 if (!pw)
1051 return NULL;
1052 if (pw->n == 0)
1053 return pw;
1054
1055 for (i = pw->n - 1; i >= 0; --i) {
1056 for (j = i - 1; j >= 0; --j) {
1057 if (!FN(EL,plain_is_equal)(pw->p[i].FIELD,
1058 pw->p[j].FIELD))
1059 continue;
1060 pw->p[j].set = isl_set_union(pw->p[j].set,
1061 pw->p[i].set);
1062 FN(EL,free)(pw->p[i].FIELD);
1063 if (i != pw->n - 1)
1064 pw->p[i] = pw->p[pw->n - 1];
1065 pw->n--;
1066 break;
1067 }
1068 if (j >= 0)
1069 continue;
1070 pw->p[i].set = isl_set_coalesce(pw->p[i].set);
1071 if (!pw->p[i].set)
1072 goto error;
1073 }
1074
1075 return pw;
1076 error:
1077 FN(PW,free)(pw);
1078 return NULL;
1079 }
1080
1081 isl_ctx *FN(PW,get_ctx)(__isl_keep PW *pw)
1082 {
1083 return pw ? isl_space_get_ctx(pw->dim) : NULL;
1084 }
1085
1086 #ifndef NO_INVOLVES_DIMS
1087 int FN(PW,involves_dims)(__isl_keep PW *pw, enum isl_dim_type type,
1088 unsigned first, unsigned n)
1089 {
1090 int i;
1091 enum isl_dim_type set_type;
1092
1093 if (!pw)
1094 return -1;
1095 if (pw->n == 0 || n == 0)
1096 return 0;
1097
1098 set_type = type == isl_dim_in ? isl_dim_set : type;
1099
1100 for (i = 0; i < pw->n; ++i) {
1101 int involves = FN(EL,involves_dims)(pw->p[i].FIELD,
1102 type, first, n);
1103 if (involves < 0 || involves)
1104 return involves;
1105 involves = isl_set_involves_dims(pw->p[i].set,
1106 set_type, first, n);
1107 if (involves < 0 || involves)
1108 return involves;
1109 }
1110 return 0;
1111 }
1112 #endif
1113
1114 __isl_give PW *FN(PW,set_dim_name)(__isl_take PW *pw,
1115 enum isl_dim_type type, unsigned pos, const char *s)
1116 {
1117 int i;
1118 enum isl_dim_type set_type;
1119
1120 pw = FN(PW,cow)(pw);
1121 if (!pw)
1122 return NULL;
1123
1124 set_type = type == isl_dim_in ? isl_dim_set : type;
1125
1126 pw->dim = isl_space_set_dim_name(pw->dim, type, pos, s);
1127 if (!pw->dim)
1128 goto error;
1129
1130 for (i = 0; i < pw->n; ++i) {
1131 pw->p[i].set = isl_set_set_dim_name(pw->p[i].set,
1132 set_type, pos, s);
1133 if (!pw->p[i].set)
1134 goto error;
1135 pw->p[i].FIELD = FN(EL,set_dim_name)(pw->p[i].FIELD, type, pos, s);
1136 if (!pw->p[i].FIELD)
1137 goto error;
1138 }
1139
1140 return pw;
1141 error:
1142 FN(PW,free)(pw);
1143 return NULL;
1144 }
1145
1146 #ifndef NO_DROP_DIMS
1147 __isl_give PW *FN(PW,drop_dims)(__isl_take PW *pw,
1148 enum isl_dim_type type, unsigned first, unsigned n)
1149 {
1150 int i;
1151 enum isl_dim_type set_type;
1152
1153 if (!pw)
1154 return NULL;
1155 if (n == 0 && !isl_space_get_tuple_name(pw->dim, type))
1156 return pw;
1157
1158 set_type = type == isl_dim_in ? isl_dim_set : type;
1159
1160 pw = FN(PW,cow)(pw);
1161 if (!pw)
1162 return NULL;
1163 pw->dim = isl_space_drop_dims(pw->dim, type, first, n);
1164 if (!pw->dim)
1165 goto error;
1166 for (i = 0; i < pw->n; ++i) {
1167 pw->p[i].FIELD = FN(EL,drop_dims)(pw->p[i].FIELD, type, first, n);
1168 if (!pw->p[i].FIELD)
1169 goto error;
1170 if (type == isl_dim_out)
1171 continue;
1172 pw->p[i].set = isl_set_drop(pw->p[i].set, set_type, first, n);
1173 if (!pw->p[i].set)
1174 goto error;
1175 }
1176
1177 return pw;
1178 error:
1179 FN(PW,free)(pw);
1180 return NULL;
1181 }
1182
1183 /* This function is very similar to drop_dims.
1184 * The only difference is that the cells may still involve
1185 * the specified dimensions. They are removed using
1186 * isl_set_project_out instead of isl_set_drop.
1187 */
1188 __isl_give PW *FN(PW,project_out)(__isl_take PW *pw,
1189 enum isl_dim_type type, unsigned first, unsigned n)
1190 {
1191 int i;
1192 enum isl_dim_type set_type;
1193
1194 if (!pw)
1195 return NULL;
1196 if (n == 0 && !isl_space_get_tuple_name(pw->dim, type))
1197 return pw;
1198
1199 set_type = type == isl_dim_in ? isl_dim_set : type;
1200
1201 pw = FN(PW,cow)(pw);
1202 if (!pw)
1203 return NULL;
1204 pw->dim = isl_space_drop_dims(pw->dim, type, first, n);
1205 if (!pw->dim)
1206 goto error;
1207 for (i = 0; i < pw->n; ++i) {
1208 pw->p[i].set = isl_set_project_out(pw->p[i].set,
1209 set_type, first, n);
1210 if (!pw->p[i].set)
1211 goto error;
1212 pw->p[i].FIELD = FN(EL,drop_dims)(pw->p[i].FIELD, type, first, n);
1213 if (!pw->p[i].FIELD)
1214 goto error;
1215 }
1216
1217 return pw;
1218 error:
1219 FN(PW,free)(pw);
1220 return NULL;
1221 }
1222
1223 /* Project the domain of pw onto its parameter space.
1224 */
1225 __isl_give PW *FN(PW,project_domain_on_params)(__isl_take PW *pw)
1226 {
1227 isl_space *space;
1228 unsigned n;
1229
1230 n = FN(PW,dim)(pw, isl_dim_in);
1231 pw = FN(PW,project_out)(pw, isl_dim_in, 0, n);
1232 space = FN(PW,get_domain_space)(pw);
1233 space = isl_space_params(space);
1234 pw = FN(PW,reset_domain_space)(pw, space);
1235 return pw;
1236 }
1237 #endif
1238
1239 #ifndef NO_INSERT_DIMS
1240 __isl_give PW *FN(PW,insert_dims)(__isl_take PW *pw, enum isl_dim_type type,
1241 unsigned first, unsigned n)
1242 {
1243 int i;
1244 enum isl_dim_type set_type;
1245
1246 if (!pw)
1247 return NULL;
1248 if (n == 0 && !isl_space_is_named_or_nested(pw->dim, type))
1249 return pw;
1250
1251 set_type = type == isl_dim_in ? isl_dim_set : type;
1252
1253 pw = FN(PW,cow)(pw);
1254 if (!pw)
1255 return NULL;
1256
1257 pw->dim = isl_space_insert_dims(pw->dim, type, first, n);
1258 if (!pw->dim)
1259 goto error;
1260
1261 for (i = 0; i < pw->n; ++i) {
1262 pw->p[i].set = isl_set_insert_dims(pw->p[i].set,
1263 set_type, first, n);
1264 if (!pw->p[i].set)
1265 goto error;
1266 pw->p[i].FIELD = FN(EL,insert_dims)(pw->p[i].FIELD,
1267 type, first, n);
1268 if (!pw->p[i].FIELD)
1269 goto error;
1270 }
1271
1272 return pw;
1273 error:
1274 FN(PW,free)(pw);
1275 return NULL;
1276 }
1277 #endif
1278
1279 __isl_give PW *FN(PW,fix_dim)(__isl_take PW *pw,
1280 enum isl_dim_type type, unsigned pos, isl_int v)
1281 {
1282 int i;
1283
1284 if (!pw)
1285 return NULL;
1286
1287 if (type == isl_dim_in)
1288 type = isl_dim_set;
1289
1290 pw = FN(PW,cow)(pw);
1291 if (!pw)
1292 return NULL;
1293 for (i = 0; i < pw->n; ++i) {
1294 pw->p[i].set = isl_set_fix(pw->p[i].set, type, pos, v);
1295 if (FN(PW,exploit_equalities_and_remove_if_empty)(pw, i) < 0)
1296 return FN(PW,free)(pw);
1297 }
1298
1299 return pw;
1300 }
1301
1302 /* Fix the value of the variable at position "pos" of type "type" of "pw"
1303 * to be equal to "v".
1304 */
1305 __isl_give PW *FN(PW,fix_val)(__isl_take PW *pw,
1306 enum isl_dim_type type, unsigned pos, __isl_take isl_val *v)
1307 {
1308 if (!v)
1309 return FN(PW,free)(pw);
1310 if (!isl_val_is_int(v))
1311 isl_die(FN(PW,get_ctx)(pw), isl_error_invalid,
1312 "expecting integer value", goto error);
1313
1314 pw = FN(PW,fix_dim)(pw, type, pos, v->n);
1315 isl_val_free(v);
1316
1317 return pw;
1318 error:
1319 isl_val_free(v);
1320 return FN(PW,free)(pw);
1321 }
1322
1323 unsigned FN(PW,dim)(__isl_keep PW *pw, enum isl_dim_type type)
1324 {
1325 return pw ? isl_space_dim(pw->dim, type) : 0;
1326 }
1327
1328 __isl_give PW *FN(PW,split_dims)(__isl_take PW *pw,
1329 enum isl_dim_type type, unsigned first, unsigned n)
1330 {
1331 int i;
1332
1333 if (!pw)
1334 return NULL;
1335 if (n == 0)
1336 return pw;
1337
1338 if (type == isl_dim_in)
1339 type = isl_dim_set;
1340
1341 pw = FN(PW,cow)(pw);
1342 if (!pw)
1343 return NULL;
1344 if (!pw->dim)
1345 goto error;
1346 for (i = 0; i < pw->n; ++i) {
1347 pw->p[i].set = isl_set_split_dims(pw->p[i].set, type, first, n);
1348 if (!pw->p[i].set)
1349 goto error;
1350 }
1351
1352 return pw;
1353 error:
1354 FN(PW,free)(pw);
1355 return NULL;
1356 }
1357
1358 #ifndef NO_OPT
1359 /* Compute the maximal value attained by the piecewise quasipolynomial
1360 * on its domain or zero if the domain is empty.
1361 * In the worst case, the domain is scanned completely,
1362 * so the domain is assumed to be bounded.
1363 */
1364 __isl_give isl_val *FN(PW,opt)(__isl_take PW *pw, int max)
1365 {
1366 int i;
1367 isl_val *opt;
1368
1369 if (!pw)
1370 return NULL;
1371
1372 if (pw->n == 0) {
1373 opt = isl_val_zero(FN(PW,get_ctx)(pw));
1374 FN(PW,free)(pw);
1375 return opt;
1376 }
1377
1378 opt = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[0].FIELD),
1379 isl_set_copy(pw->p[0].set), max);
1380 for (i = 1; i < pw->n; ++i) {
1381 isl_val *opt_i;
1382 opt_i = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[i].FIELD),
1383 isl_set_copy(pw->p[i].set), max);
1384 if (max)
1385 opt = isl_val_max(opt, opt_i);
1386 else
1387 opt = isl_val_min(opt, opt_i);
1388 }
1389
1390 FN(PW,free)(pw);
1391 return opt;
1392 }
1393
1394 __isl_give isl_val *FN(PW,max)(__isl_take PW *pw)
1395 {
1396 return FN(PW,opt)(pw, 1);
1397 }
1398
1399 __isl_give isl_val *FN(PW,min)(__isl_take PW *pw)
1400 {
1401 return FN(PW,opt)(pw, 0);
1402 }
1403 #endif
1404
1405 __isl_give isl_space *FN(PW,get_space)(__isl_keep PW *pw)
1406 {
1407 return pw ? isl_space_copy(pw->dim) : NULL;
1408 }
1409
1410 __isl_give isl_space *FN(PW,get_domain_space)(__isl_keep PW *pw)
1411 {
1412 return pw ? isl_space_domain(isl_space_copy(pw->dim)) : NULL;
1413 }
1414
1415 /* Return the position of the dimension of the given type and name
1416 * in "pw".
1417 * Return -1 if no such dimension can be found.
1418 */
1419 int FN(PW,find_dim_by_name)(__isl_keep PW *pw,
1420 enum isl_dim_type type, const char *name)
1421 {
1422 if (!pw)
1423 return -1;
1424 return isl_space_find_dim_by_name(pw->dim, type, name);
1425 }
1426
1427 #ifndef NO_RESET_DIM
1428 /* Reset the space of "pw". Since we don't know if the elements
1429 * represent the spaces themselves or their domains, we pass along
1430 * both when we call their reset_space_and_domain.
1431 */
1432 static __isl_give PW *FN(PW,reset_space_and_domain)(__isl_take PW *pw,
1433 __isl_take isl_space *space, __isl_take isl_space *domain)
1434 {
1435 int i;
1436
1437 pw = FN(PW,cow)(pw);
1438 if (!pw || !space || !domain)
1439 goto error;
1440
1441 for (i = 0; i < pw->n; ++i) {
1442 pw->p[i].set = isl_set_reset_space(pw->p[i].set,
1443 isl_space_copy(domain));
1444 if (!pw->p[i].set)
1445 goto error;
1446 pw->p[i].FIELD = FN(EL,reset_space_and_domain)(pw->p[i].FIELD,
1447 isl_space_copy(space), isl_space_copy(domain));
1448 if (!pw->p[i].FIELD)
1449 goto error;
1450 }
1451
1452 isl_space_free(domain);
1453
1454 isl_space_free(pw->dim);
1455 pw->dim = space;
1456
1457 return pw;
1458 error:
1459 isl_space_free(domain);
1460 isl_space_free(space);
1461 FN(PW,free)(pw);
1462 return NULL;
1463 }
1464
1465 __isl_give PW *FN(PW,reset_domain_space)(__isl_take PW *pw,
1466 __isl_take isl_space *domain)
1467 {
1468 isl_space *space;
1469
1470 space = isl_space_extend_domain_with_range(isl_space_copy(domain),
1471 FN(PW,get_space)(pw));
1472 return FN(PW,reset_space_and_domain)(pw, space, domain);
1473 }
1474
1475 __isl_give PW *FN(PW,reset_space)(__isl_take PW *pw, __isl_take isl_space *dim)
1476 {
1477 isl_space *domain;
1478
1479 domain = isl_space_domain(isl_space_copy(dim));
1480 return FN(PW,reset_space_and_domain)(pw, dim, domain);
1481 }
1482
1483 __isl_give PW *FN(PW,set_tuple_id)(__isl_take PW *pw, enum isl_dim_type type,
1484 __isl_take isl_id *id)
1485 {
1486 isl_space *space;
1487
1488 pw = FN(PW,cow)(pw);
1489 if (!pw)
1490 goto error;
1491
1492 space = FN(PW,get_space)(pw);
1493 space = isl_space_set_tuple_id(space, type, id);
1494
1495 return FN(PW,reset_space)(pw, space);
1496 error:
1497 isl_id_free(id);
1498 return FN(PW,free)(pw);
1499 }
1500
1501 /* Drop the id on the specified tuple.
1502 */
1503 __isl_give PW *FN(PW,reset_tuple_id)(__isl_take PW *pw, enum isl_dim_type type)
1504 {
1505 isl_space *space;
1506
1507 if (!pw)
1508 return NULL;
1509 if (!FN(PW,has_tuple_id)(pw, type))
1510 return pw;
1511
1512 pw = FN(PW,cow)(pw);
1513 if (!pw)
1514 return NULL;
1515
1516 space = FN(PW,get_space)(pw);
1517 space = isl_space_reset_tuple_id(space, type);
1518
1519 return FN(PW,reset_space)(pw, space);
1520 }
1521
1522 __isl_give PW *FN(PW,set_dim_id)(__isl_take PW *pw,
1523 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
1524 {
1525 pw = FN(PW,cow)(pw);
1526 if (!pw)
1527 goto error;
1528 pw->dim = isl_space_set_dim_id(pw->dim, type, pos, id);
1529 return FN(PW,reset_space)(pw, isl_space_copy(pw->dim));
1530 error:
1531 isl_id_free(id);
1532 return FN(PW,free)(pw);
1533 }
1534 #endif
1535
1536 int FN(PW,has_equal_space)(__isl_keep PW *pw1, __isl_keep PW *pw2)
1537 {
1538 if (!pw1 || !pw2)
1539 return -1;
1540
1541 return isl_space_is_equal(pw1->dim, pw2->dim);
1542 }
1543
1544 #ifndef NO_MORPH
1545 __isl_give PW *FN(PW,morph_domain)(__isl_take PW *pw,
1546 __isl_take isl_morph *morph)
1547 {
1548 int i;
1549 isl_ctx *ctx;
1550
1551 if (!pw || !morph)
1552 goto error;
1553
1554 ctx = isl_space_get_ctx(pw->dim);
1555 isl_assert(ctx, isl_space_is_domain_internal(morph->dom->dim, pw->dim),
1556 goto error);
1557
1558 pw = FN(PW,cow)(pw);
1559 if (!pw)
1560 goto error;
1561 pw->dim = isl_space_extend_domain_with_range(
1562 isl_space_copy(morph->ran->dim), pw->dim);
1563 if (!pw->dim)
1564 goto error;
1565
1566 for (i = 0; i < pw->n; ++i) {
1567 pw->p[i].set = isl_morph_set(isl_morph_copy(morph), pw->p[i].set);
1568 if (!pw->p[i].set)
1569 goto error;
1570 pw->p[i].FIELD = FN(EL,morph_domain)(pw->p[i].FIELD,
1571 isl_morph_copy(morph));
1572 if (!pw->p[i].FIELD)
1573 goto error;
1574 }
1575
1576 isl_morph_free(morph);
1577
1578 return pw;
1579 error:
1580 FN(PW,free)(pw);
1581 isl_morph_free(morph);
1582 return NULL;
1583 }
1584 #endif
1585
1586 int FN(PW,n_piece)(__isl_keep PW *pw)
1587 {
1588 return pw ? pw->n : 0;
1589 }
1590
1591 int FN(PW,foreach_piece)(__isl_keep PW *pw,
1592 int (*fn)(__isl_take isl_set *set, __isl_take EL *el, void *user),
1593 void *user)
1594 {
1595 int i;
1596
1597 if (!pw)
1598 return -1;
1599
1600 for (i = 0; i < pw->n; ++i)
1601 if (fn(isl_set_copy(pw->p[i].set),
1602 FN(EL,copy)(pw->p[i].FIELD), user) < 0)
1603 return -1;
1604
1605 return 0;
1606 }
1607
1608 #ifndef NO_LIFT
1609 static int any_divs(__isl_keep isl_set *set)
1610 {
1611 int i;
1612
1613 if (!set)
1614 return -1;
1615
1616 for (i = 0; i < set->n; ++i)
1617 if (set->p[i]->n_div > 0)
1618 return 1;
1619
1620 return 0;
1621 }
1622
1623 static int foreach_lifted_subset(__isl_take isl_set *set, __isl_take EL *el,
1624 int (*fn)(__isl_take isl_set *set, __isl_take EL *el,
1625 void *user), void *user)
1626 {
1627 int i;
1628
1629 if (!set || !el)
1630 goto error;
1631
1632 for (i = 0; i < set->n; ++i) {
1633 isl_set *lift;
1634 EL *copy;
1635
1636 lift = isl_set_from_basic_set(isl_basic_set_copy(set->p[i]));
1637 lift = isl_set_lift(lift);
1638
1639 copy = FN(EL,copy)(el);
1640 copy = FN(EL,lift)(copy, isl_set_get_space(lift));
1641
1642 if (fn(lift, copy, user) < 0)
1643 goto error;
1644 }
1645
1646 isl_set_free(set);
1647 FN(EL,free)(el);
1648
1649 return 0;
1650 error:
1651 isl_set_free(set);
1652 FN(EL,free)(el);
1653 return -1;
1654 }
1655
1656 int FN(PW,foreach_lifted_piece)(__isl_keep PW *pw,
1657 int (*fn)(__isl_take isl_set *set, __isl_take EL *el,
1658 void *user), void *user)
1659 {
1660 int i;
1661
1662 if (!pw)
1663 return -1;
1664
1665 for (i = 0; i < pw->n; ++i) {
1666 isl_set *set;
1667 EL *el;
1668
1669 set = isl_set_copy(pw->p[i].set);
1670 el = FN(EL,copy)(pw->p[i].FIELD);
1671 if (!any_divs(set)) {
1672 if (fn(set, el, user) < 0)
1673 return -1;
1674 continue;
1675 }
1676 if (foreach_lifted_subset(set, el, fn, user) < 0)
1677 return -1;
1678 }
1679
1680 return 0;
1681 }
1682 #endif
1683
1684 #ifndef NO_MOVE_DIMS
1685 __isl_give PW *FN(PW,move_dims)(__isl_take PW *pw,
1686 enum isl_dim_type dst_type, unsigned dst_pos,
1687 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1688 {
1689 int i;
1690
1691 pw = FN(PW,cow)(pw);
1692 if (!pw)
1693 return NULL;
1694
1695 pw->dim = isl_space_move_dims(pw->dim, dst_type, dst_pos, src_type, src_pos, n);
1696 if (!pw->dim)
1697 goto error;
1698
1699 for (i = 0; i < pw->n; ++i) {
1700 pw->p[i].FIELD = FN(EL,move_dims)(pw->p[i].FIELD,
1701 dst_type, dst_pos, src_type, src_pos, n);
1702 if (!pw->p[i].FIELD)
1703 goto error;
1704 }
1705
1706 if (dst_type == isl_dim_in)
1707 dst_type = isl_dim_set;
1708 if (src_type == isl_dim_in)
1709 src_type = isl_dim_set;
1710
1711 for (i = 0; i < pw->n; ++i) {
1712 pw->p[i].set = isl_set_move_dims(pw->p[i].set,
1713 dst_type, dst_pos,
1714 src_type, src_pos, n);
1715 if (!pw->p[i].set)
1716 goto error;
1717 }
1718
1719 return pw;
1720 error:
1721 FN(PW,free)(pw);
1722 return NULL;
1723 }
1724 #endif
1725
1726 __isl_give PW *FN(PW,mul_isl_int)(__isl_take PW *pw, isl_int v)
1727 {
1728 int i;
1729
1730 if (isl_int_is_one(v))
1731 return pw;
1732 if (pw && DEFAULT_IS_ZERO && isl_int_is_zero(v)) {
1733 PW *zero;
1734 isl_space *dim = FN(PW,get_space)(pw);
1735 #ifdef HAS_TYPE
1736 zero = FN(PW,ZERO)(dim, pw->type);
1737 #else
1738 zero = FN(PW,ZERO)(dim);
1739 #endif
1740 FN(PW,free)(pw);
1741 return zero;
1742 }
1743 pw = FN(PW,cow)(pw);
1744 if (!pw)
1745 return NULL;
1746 if (pw->n == 0)
1747 return pw;
1748
1749 #ifdef HAS_TYPE
1750 if (isl_int_is_neg(v))
1751 pw->type = isl_fold_type_negate(pw->type);
1752 #endif
1753 for (i = 0; i < pw->n; ++i) {
1754 pw->p[i].FIELD = FN(EL,scale)(pw->p[i].FIELD, v);
1755 if (!pw->p[i].FIELD)
1756 goto error;
1757 }
1758
1759 return pw;
1760 error:
1761 FN(PW,free)(pw);
1762 return NULL;
1763 }
1764
1765 /* Multiply the pieces of "pw" by "v" and return the result.
1766 */
1767 __isl_give PW *FN(PW,scale_val)(__isl_take PW *pw, __isl_take isl_val *v)
1768 {
1769 int i;
1770
1771 if (!pw || !v)
1772 goto error;
1773
1774 if (isl_val_is_one(v)) {
1775 isl_val_free(v);
1776 return pw;
1777 }
1778 if (pw && DEFAULT_IS_ZERO && isl_val_is_zero(v)) {
1779 PW *zero;
1780 isl_space *space = FN(PW,get_space)(pw);
1781 #ifdef HAS_TYPE
1782 zero = FN(PW,ZERO)(space, pw->type);
1783 #else
1784 zero = FN(PW,ZERO)(space);
1785 #endif
1786 FN(PW,free)(pw);
1787 isl_val_free(v);
1788 return zero;
1789 }
1790 if (pw->n == 0) {
1791 isl_val_free(v);
1792 return pw;
1793 }
1794 pw = FN(PW,cow)(pw);
1795 if (!pw)
1796 goto error;
1797
1798 #ifdef HAS_TYPE
1799 if (isl_val_is_neg(v))
1800 pw->type = isl_fold_type_negate(pw->type);
1801 #endif
1802 for (i = 0; i < pw->n; ++i) {
1803 pw->p[i].FIELD = FN(EL,scale_val)(pw->p[i].FIELD,
1804 isl_val_copy(v));
1805 if (!pw->p[i].FIELD)
1806 goto error;
1807 }
1808
1809 isl_val_free(v);
1810 return pw;
1811 error:
1812 isl_val_free(v);
1813 FN(PW,free)(pw);
1814 return NULL;
1815 }
1816
1817 /* Divide the pieces of "pw" by "v" and return the result.
1818 */
1819 __isl_give PW *FN(PW,scale_down_val)(__isl_take PW *pw, __isl_take isl_val *v)
1820 {
1821 int i;
1822
1823 if (!pw || !v)
1824 goto error;
1825
1826 if (isl_val_is_one(v)) {
1827 isl_val_free(v);
1828 return pw;
1829 }
1830
1831 if (!isl_val_is_rat(v))
1832 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1833 "expecting rational factor", goto error);
1834 if (isl_val_is_zero(v))
1835 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1836 "cannot scale down by zero", goto error);
1837
1838 if (pw->n == 0) {
1839 isl_val_free(v);
1840 return pw;
1841 }
1842 pw = FN(PW,cow)(pw);
1843 if (!pw)
1844 goto error;
1845
1846 #ifdef HAS_TYPE
1847 if (isl_val_is_neg(v))
1848 pw->type = isl_fold_type_negate(pw->type);
1849 #endif
1850 for (i = 0; i < pw->n; ++i) {
1851 pw->p[i].FIELD = FN(EL,scale_down_val)(pw->p[i].FIELD,
1852 isl_val_copy(v));
1853 if (!pw->p[i].FIELD)
1854 goto error;
1855 }
1856
1857 isl_val_free(v);
1858 return pw;
1859 error:
1860 isl_val_free(v);
1861 FN(PW,free)(pw);
1862 return NULL;
1863 }
1864
1865 __isl_give PW *FN(PW,scale)(__isl_take PW *pw, isl_int v)
1866 {
1867 return FN(PW,mul_isl_int)(pw, v);
1868 }
1869
1870 static int FN(PW,qsort_set_cmp)(const void *p1, const void *p2)
1871 {
1872 isl_set *set1 = *(isl_set * const *)p1;
1873 isl_set *set2 = *(isl_set * const *)p2;
1874
1875 return isl_set_plain_cmp(set1, set2);
1876 }
1877
1878 /* We normalize in place, but if anything goes wrong we need
1879 * to return NULL, so we need to make sure we don't change the
1880 * meaning of any possible other copies of map.
1881 */
1882 __isl_give PW *FN(PW,normalize)(__isl_take PW *pw)
1883 {
1884 int i, j;
1885 isl_set *set;
1886
1887 if (!pw)
1888 return NULL;
1889 for (i = 0; i < pw->n; ++i) {
1890 set = isl_set_normalize(isl_set_copy(pw->p[i].set));
1891 if (!set)
1892 return FN(PW,free)(pw);
1893 isl_set_free(pw->p[i].set);
1894 pw->p[i].set = set;
1895 }
1896 qsort(pw->p, pw->n, sizeof(pw->p[0]), &FN(PW,qsort_set_cmp));
1897 for (i = pw->n - 1; i >= 1; --i) {
1898 if (!isl_set_plain_is_equal(pw->p[i - 1].set, pw->p[i].set))
1899 continue;
1900 if (!FN(EL,plain_is_equal)(pw->p[i - 1].FIELD, pw->p[i].FIELD))
1901 continue;
1902 set = isl_set_union(isl_set_copy(pw->p[i - 1].set),
1903 isl_set_copy(pw->p[i].set));
1904 if (!set)
1905 return FN(PW,free)(pw);
1906 isl_set_free(pw->p[i].set);
1907 FN(EL,free)(pw->p[i].FIELD);
1908 isl_set_free(pw->p[i - 1].set);
1909 pw->p[i - 1].set = set;
1910 for (j = i + 1; j < pw->n; ++j)
1911 pw->p[j - 1] = pw->p[j];
1912 pw->n--;
1913 }
1914
1915 return pw;
1916 }
1917
1918 /* Is pw1 obviously equal to pw2?
1919 * That is, do they have obviously identical cells and obviously identical
1920 * elements on each cell?
1921 */
1922 int FN(PW,plain_is_equal)(__isl_keep PW *pw1, __isl_keep PW *pw2)
1923 {
1924 int i;
1925 int equal;
1926
1927 if (!pw1 || !pw2)
1928 return -1;
1929
1930 if (pw1 == pw2)
1931 return 1;
1932 if (!isl_space_is_equal(pw1->dim, pw2->dim))
1933 return 0;
1934
1935 pw1 = FN(PW,copy)(pw1);
1936 pw2 = FN(PW,copy)(pw2);
1937 pw1 = FN(PW,normalize)(pw1);
1938 pw2 = FN(PW,normalize)(pw2);
1939 if (!pw1 || !pw2)
1940 goto error;
1941
1942 equal = pw1->n == pw2->n;
1943 for (i = 0; equal && i < pw1->n; ++i) {
1944 equal = isl_set_plain_is_equal(pw1->p[i].set, pw2->p[i].set);
1945 if (equal < 0)
1946 goto error;
1947 if (!equal)
1948 break;
1949 equal = FN(EL,plain_is_equal)(pw1->p[i].FIELD, pw2->p[i].FIELD);
1950 if (equal < 0)
1951 goto error;
1952 }
1953
1954 FN(PW,free)(pw1);
1955 FN(PW,free)(pw2);
1956 return equal;
1957 error:
1958 FN(PW,free)(pw1);
1959 FN(PW,free)(pw2);
1960 return -1;
1961 }
1962
1963 #ifndef NO_PULLBACK
1964 static __isl_give PW *FN(PW,align_params_pw_multi_aff_and)(__isl_take PW *pw,
1965 __isl_take isl_multi_aff *ma,
1966 __isl_give PW *(*fn)(__isl_take PW *pw, __isl_take isl_multi_aff *ma))
1967 {
1968 isl_ctx *ctx;
1969 isl_space *ma_space;
1970
1971 ma_space = isl_multi_aff_get_space(ma);
1972 if (!pw || !ma || !ma_space)
1973 goto error;
1974 if (isl_space_match(pw->dim, isl_dim_param, ma_space, isl_dim_param)) {
1975 isl_space_free(ma_space);
1976 return fn(pw, ma);
1977 }
1978 ctx = FN(PW,get_ctx)(pw);
1979 if (!isl_space_has_named_params(pw->dim) ||
1980 !isl_space_has_named_params(ma_space))
1981 isl_die(ctx, isl_error_invalid,
1982 "unaligned unnamed parameters", goto error);
1983 pw = FN(PW,align_params)(pw, ma_space);
1984 ma = isl_multi_aff_align_params(ma, FN(PW,get_space)(pw));
1985 return fn(pw, ma);
1986 error:
1987 isl_space_free(ma_space);
1988 FN(PW,free)(pw);
1989 isl_multi_aff_free(ma);
1990 return NULL;
1991 }
1992
1993 static __isl_give PW *FN(PW,align_params_pw_pw_multi_aff_and)(__isl_take PW *pw,
1994 __isl_take isl_pw_multi_aff *pma,
1995 __isl_give PW *(*fn)(__isl_take PW *pw,
1996 __isl_take isl_pw_multi_aff *ma))
1997 {
1998 isl_ctx *ctx;
1999 isl_space *pma_space;
2000
2001 pma_space = isl_pw_multi_aff_get_space(pma);
2002 if (!pw || !pma || !pma_space)
2003 goto error;
2004 if (isl_space_match(pw->dim, isl_dim_param, pma_space, isl_dim_param)) {
2005 isl_space_free(pma_space);
2006 return fn(pw, pma);
2007 }
2008 ctx = FN(PW,get_ctx)(pw);
2009 if (!isl_space_has_named_params(pw->dim) ||
2010 !isl_space_has_named_params(pma_space))
2011 isl_die(ctx, isl_error_invalid,
2012 "unaligned unnamed parameters", goto error);
2013 pw = FN(PW,align_params)(pw, pma_space);
2014 pma = isl_pw_multi_aff_align_params(pma, FN(PW,get_space)(pw));
2015 return fn(pw, pma);
2016 error:
2017 isl_space_free(pma_space);
2018 FN(PW,free)(pw);
2019 isl_pw_multi_aff_free(pma);
2020 return NULL;
2021 }
2022
2023 /* Compute the pullback of "pw" by the function represented by "ma".
2024 * In other words, plug in "ma" in "pw".
2025 */
2026 static __isl_give PW *FN(PW,pullback_multi_aff_aligned)(__isl_take PW *pw,
2027 __isl_take isl_multi_aff *ma)
2028 {
2029 int i;
2030 isl_space *space = NULL;
2031
2032 ma = isl_multi_aff_align_divs(ma);
2033 pw = FN(PW,cow)(pw);
2034 if (!pw || !ma)
2035 goto error;
2036
2037 space = isl_space_join(isl_multi_aff_get_space(ma),
2038 FN(PW,get_space)(pw));
2039
2040 for (i = 0; i < pw->n; ++i) {
2041 pw->p[i].set = isl_set_preimage_multi_aff(pw->p[i].set,
2042 isl_multi_aff_copy(ma));
2043 if (!pw->p[i].set)
2044 goto error;
2045 pw->p[i].FIELD = FN(EL,pullback_multi_aff)(pw->p[i].FIELD,
2046 isl_multi_aff_copy(ma));
2047 if (!pw->p[i].FIELD)
2048 goto error;
2049 }
2050
2051 pw = FN(PW,reset_space)(pw, space);
2052 isl_multi_aff_free(ma);
2053 return pw;
2054 error:
2055 isl_space_free(space);
2056 isl_multi_aff_free(ma);
2057 FN(PW,free)(pw);
2058 return NULL;
2059 }
2060
2061 __isl_give PW *FN(PW,pullback_multi_aff)(__isl_take PW *pw,
2062 __isl_take isl_multi_aff *ma)
2063 {
2064 return FN(PW,align_params_pw_multi_aff_and)(pw, ma,
2065 &FN(PW,pullback_multi_aff_aligned));
2066 }
2067
2068 /* Compute the pullback of "pw" by the function represented by "pma".
2069 * In other words, plug in "pma" in "pw".
2070 */
2071 static __isl_give PW *FN(PW,pullback_pw_multi_aff_aligned)(__isl_take PW *pw,
2072 __isl_take isl_pw_multi_aff *pma)
2073 {
2074 int i;
2075 PW *res;
2076
2077 if (!pma)
2078 goto error;
2079
2080 if (pma->n == 0) {
2081 isl_space *space;
2082 space = isl_space_join(isl_pw_multi_aff_get_space(pma),
2083 FN(PW,get_space)(pw));
2084 isl_pw_multi_aff_free(pma);
2085 res = FN(PW,empty)(space);
2086 FN(PW,free)(pw);
2087 return res;
2088 }
2089
2090 res = FN(PW,pullback_multi_aff)(FN(PW,copy)(pw),
2091 isl_multi_aff_copy(pma->p[0].maff));
2092 res = FN(PW,intersect_domain)(res, isl_set_copy(pma->p[0].set));
2093
2094 for (i = 1; i < pma->n; ++i) {
2095 PW *res_i;
2096
2097 res_i = FN(PW,pullback_multi_aff)(FN(PW,copy)(pw),
2098 isl_multi_aff_copy(pma->p[i].maff));
2099 res_i = FN(PW,intersect_domain)(res_i,
2100 isl_set_copy(pma->p[i].set));
2101 res = FN(PW,add_disjoint)(res, res_i);
2102 }
2103
2104 isl_pw_multi_aff_free(pma);
2105 FN(PW,free)(pw);
2106 return res;
2107 error:
2108 isl_pw_multi_aff_free(pma);
2109 FN(PW,free)(pw);
2110 return NULL;
2111 }
2112
2113 __isl_give PW *FN(PW,pullback_pw_multi_aff)(__isl_take PW *pw,
2114 __isl_take isl_pw_multi_aff *pma)
2115 {
2116 return FN(PW,align_params_pw_pw_multi_aff_and)(pw, pma,
2117 &FN(PW,pullback_pw_multi_aff_aligned));
2118 }
2119 #endif
Integer set library