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