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