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