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
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;
44error:
45 isl_space_free(space);
46 return NULL;
47}
48
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), n: 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 */
60static __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(space: el_dim);
82 return pw;
83error:
84 isl_space_free(space: el_dim);
85 FN(PW,free)(pwqp: pw);
86 isl_set_free(set);
87 FN(EL,free)(qp: 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 */
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)(qp: 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)(qp: el);
109 if (skip < 0)
110 return FN(PW,free)(pwqp: pw);
111 return pw;
112}
113
114/* Does the space of "set" correspond to that of the domain of "el".
115 */
116static 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)(qp: el);
126 ok = isl_space_is_domain_internal(space1: set_space, space2: el_space);
127 isl_space_free(space: el_space);
128 isl_space_free(space: set_space);
129 return ok;
130}
131
132/* Check that the space of "set" corresponds to that of the domain of "el".
133 */
134static 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
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)(qp: el) OPT_TYPE_ARG(NO_LOC), n: 1);
158
159 return FN(PW,add_piece)(pw, set, el);
160error:
161 isl_set_free(set);
162 FN(EL,free)(qp: el);
163 return NULL;
164}
165
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)(space: isl_space_copy(space: pw->dim)
175 OPT_TYPE_ARG(pw->), n: pw->n);
176 if (!dup)
177 return NULL;
178
179 for (i = 0; i < pw->n; ++i)
180 dup = FN(PW,add_dup_piece)(pw: dup, set: isl_set_copy(set: pw->p[i].set),
181 FN(EL,copy)(qp: pw->p[i].FIELD));
182
183 return dup;
184}
185
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
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
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(set: pw->p[i].set);
217 FN(EL,free)(qp: pw->p[i].FIELD);
218 }
219 isl_space_free(space: pw->dim);
220 free(ptr: pw);
221
222 return NULL;
223}
224
225/* Return the space of "pw".
226 */
227__isl_keep isl_space *FN(PW,peek_space)(__isl_keep PW *pw)
228{
229 return pw ? pw->dim : NULL;
230}
231
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 */
246static __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 */
264static __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(space: pw->dim);
279 pw->dim = space;
280
281 return pw;
282error:
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 */
290static 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 */
302static __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 */
311static __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 */
326static __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 */
347static __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(set: domain);
355 return pw;
356 }
357
358 pw = FN(PW,cow)(pw);
359 if (!pw)
360 goto error;
361 isl_set_free(set: pw->p[pos].set);
362 pw->p[pos].set = domain;
363
364 return pw;
365error:
366 FN(PW,free)(pw);
367 isl_set_free(set: domain);
368 return NULL;
369}
370
371/* Return the base expression associated to
372 * the cell at position "pos" in "pw".
373 */
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 */
384static __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 */
400static __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 */
425static __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)(qp: 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)(qp: pw->p[pos].FIELD);
441 pw->p[pos].FIELD = el;
442
443 return pw;
444error:
445 FN(PW,free)(pw);
446 FN(EL,free)(qp: 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 */
455static __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, inplace: 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 */
468static __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, inplace: 1);
472}
473
474/* Create a piecewise expression with the given base expression on a universe
475 * domain.
476 */
477static __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)(qp: el));
481 return FN(PW,alloc)(OPT_TYPE_ARG_FIRST(NO_LOC) set: 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 */
491static __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)(qp: 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)(qp: el);
507 FN(EL,free)(qp: el);
508 return FN(PW,ZERO)(space OPT_TYPE_ARG(NO_LOC));
509error:
510 FN(EL,free)(qp: 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 */
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
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
533const 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(space: pw->dim, type, pos) : NULL;
537}
538
539isl_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(space: pw->dim, type, pos) : isl_bool_error;
543}
544
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(space: pw->dim, type, pos) : NULL;
549}
550
551isl_bool FN(PW,has_tuple_name)(__isl_keep PW *pw, enum isl_dim_type type)
552{
553 return pw ? isl_space_has_tuple_name(space: pw->dim, type) : isl_bool_error;
554}
555
556const char *FN(PW,get_tuple_name)(__isl_keep PW *pw, enum isl_dim_type type)
557{
558 return pw ? isl_space_get_tuple_name(space: pw->dim, type) : NULL;
559}
560
561isl_bool FN(PW,has_tuple_id)(__isl_keep PW *pw, enum isl_dim_type type)
562{
563 return pw ? isl_space_has_tuple_id(space: pw->dim, type) : isl_bool_error;
564}
565
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(space: pw->dim, type) : NULL;
569}
570
571isl_bool FN(PW,IS_ZERO)(__isl_keep PW *pw)
572{
573 if (!pw)
574 return isl_bool_error;
575
576 return isl_bool_ok(b: pw->n == 0);
577}
578
579static __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)(pwqp: 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, pos: i);
594 domain = isl_set_realign(set: domain, r: isl_reordering_copy(exp));
595 pw = FN(PW,restore_domain_at)(pw, pos: i, domain);
596
597 el = FN(PW,take_base_at)(pw, pos: i);
598 el = FN(EL,realign_domain)(qp: el, r: isl_reordering_copy(exp));
599 pw = FN(PW,restore_base_at)(pw, pos: i, el);
600 }
601
602 pw = FN(PW,reset_domain_space)(pwqp: pw, space: isl_reordering_get_space(r: exp));
603
604 isl_reordering_free(exp);
605 return pw;
606error:
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 */
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(space: model);
628 if (!isl_space_has_named_params(space: model))
629 isl_die(ctx, isl_error_invalid,
630 "model has unnamed parameters", goto error);
631 if (FN(PW,check_named_params)(obj: pw) < 0)
632 goto error;
633 equal_params = isl_space_has_equal_params(space1: pw->dim, space2: 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)(pwqp: pw);
641 exp = isl_parameter_alignment_reordering(alignee: space, aligner: model);
642 isl_space_free(space);
643 pw = FN(PW,realign_domain)(pw, exp);
644 }
645
646 isl_space_free(space: model);
647 return pw;
648error:
649 isl_space_free(space: model);
650 FN(PW,free)(pw);
651 return NULL;
652}
653
654#undef TYPE
655#define TYPE PW
656
657static
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
667static
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 */
679static __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)(obj1: &pw1, obj2: &pw2) < 0)
687 goto error;
688
689 ctx = isl_space_get_ctx(space: 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)(obj1: pw1, obj2: pw2) < 0)
694 goto error;
695
696 if (FN(PW,IS_ZERO)(pw: pw1)) {
697 FN(PW,free)(pw: pw1);
698 return pw2;
699 }
700
701 if (FN(PW,IS_ZERO)(pw: pw2)) {
702 FN(PW,free)(pw: pw2);
703 return pw1;
704 }
705
706 n = (pw1->n + 1) * (pw2->n + 1);
707 res = FN(PW,alloc_size)(space: isl_space_copy(space: pw1->dim)
708 OPT_TYPE_ARG(pw1->), n);
709
710 for (i = 0; i < pw1->n; ++i) {
711 set = isl_set_copy(set: 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(set1: isl_set_copy(set: pw1->p[i].set),
716 set2: isl_set_copy(set: pw2->p[j].set));
717 if (isl_set_plain_is_empty(set: common)) {
718 isl_set_free(set: common);
719 continue;
720 }
721 set = isl_set_subtract(set1: set,
722 set2: isl_set_copy(set: pw2->p[j].set));
723
724 sum = FN(EL,add_on_domain)(dom: common,
725 FN(EL,copy)(qp: pw1->p[i].FIELD),
726 FN(EL,copy)(qp: pw2->p[j].FIELD));
727
728 res = FN(PW,add_piece)(pw: res, set: common, el: sum);
729 }
730 res = FN(PW,add_piece)(pw: res, set, FN(EL,copy)(qp: pw1->p[i].FIELD));
731 }
732
733 for (j = 0; j < pw2->n; ++j) {
734 set = isl_set_copy(set: pw2->p[j].set);
735 for (i = 0; i < pw1->n; ++i)
736 set = isl_set_subtract(set1: set,
737 set2: isl_set_copy(set: pw1->p[i].set));
738 res = FN(PW,add_piece)(pw: res, set, FN(EL,copy)(qp: pw2->p[j].FIELD));
739 }
740
741 FN(PW,free)(pw: pw1);
742 FN(PW,free)(pw: pw2);
743
744 return res;
745error:
746 FN(PW,free)(pw: pw1);
747 FN(PW,free)(pw: 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 */
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 */
770static __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 */
778static __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)(space: 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 set1: isl_set_copy(set: pw1->p[i].set),
799 set2: isl_set_copy(set: pw2->p[j].set));
800 empty = isl_set_plain_is_empty(set: common);
801 if (empty < 0 || empty) {
802 isl_set_free(set: common);
803 if (empty < 0)
804 goto error;
805 continue;
806 }
807
808 res_ij = fn(FN(EL,copy)(qp: pw1->p[i].FIELD),
809 FN(EL,copy)(qp: pw2->p[j].FIELD));
810 res_ij = FN(EL,gist)(qp: res_ij, context: isl_set_copy(set: common));
811
812 res = FN(PW,add_piece)(pw: res, set: common, el: res_ij);
813 }
814 }
815
816 isl_space_free(space);
817 FN(PW,free)(pw: pw1);
818 FN(PW,free)(pw: pw2);
819 return res;
820error:
821 isl_space_free(space);
822 FN(PW,free)(pw: pw1);
823 FN(PW,free)(pw: pw2);
824 FN(PW,free)(pw: res);
825 return NULL;
826}
827
828/* This function is currently only used from isl_aff.c
829 */
830static __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 */
838static __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)(obj1: pw1, obj2: pw2) < 0)
845 goto error;
846
847 space = isl_space_copy(space: pw1->dim);
848 return FN(PW,on_shared_domain_in)(pw1, pw2, space, fn);
849error:
850 FN(PW,free)(pw: pw1);
851 FN(PW,free)(pw: pw2);
852 return NULL;
853}
854
855/* Return the parameter domain of "pw".
856 */
857__isl_give isl_set *FN(PW,params)(__isl_take PW *pw)
858{
859 return isl_set_params(FN(PW,domain)(pwqp: pw));
860}
861
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)(pwqp: pw));
871 for (i = 0; i < pw->n; ++i)
872 dom = isl_set_union_disjoint(set1: dom, set2: isl_set_copy(set: 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 */
884static __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, pos: i);
893 empty = isl_set_plain_is_empty(set: domain);
894 if (empty < 0)
895 return FN(PW,free)(pw);
896 if (empty) {
897 isl_set_free(set: pw->p[i].set);
898 FN(EL,free)(qp: 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, pos: i));
907 el = FN(PW,take_base_at)(pw, pos: i);
908 el = FN(EL,substitute_equalities)(qp: el, eq: aff);
909 pw = FN(PW,restore_base_at_inplace)(pw, pos: 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 */
919static __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)(obj1: &pw, obj2: &set);
928 n = FN(PW,n_piece)(pwqp: 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, pos: i);
936 domain = fn(domain, isl_set_copy(set));
937 pw = FN(PW,restore_domain_at)(pw, pos: i, domain);
938 pw = FN(PW,exploit_equalities_and_remove_if_empty)(pw, i);
939 }
940
941 isl_set_free(set);
942 return pw;
943error:
944 isl_set_free(set);
945 FN(PW,free)(pw);
946 return NULL;
947}
948
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, set: context, fn: &isl_set_intersect);
953}
954
955/* Intersect the domain of "pw" with the parameter domain "context".
956 */
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, set: context, fn: &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 */
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 fn: &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 */
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, fn: &isl_set_intersect_factor_range);
980}
981
982/* Subtract "domain' from the domain of "pw".
983 */
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, set: domain, fn: &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 */
996static 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)(qp1: pc1->FIELD, qp2: 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 */
1013static __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(pbase: pw->p, total_elems: pw->n, size: sizeof(pw->p[0]),
1023 cmp: &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, pos: i);
1031 el_prev = FN(PW,peek_base_at)(pw, pos: i - 1);
1032 equal = FN(EL,plain_is_equal)(qp1: el, qp2: 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, pos: i);
1038 set_prev = FN(PW,get_domain_at)(pw, pos: i - 1);
1039 set = isl_set_union(set1: set_prev, set2: set);
1040 if (!set)
1041 return FN(PW,free)(pw);
1042 isl_set_free(set: pw->p[i].set);
1043 FN(EL,free)(qp: pw->p[i].FIELD);
1044 isl_set_free(set: 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 */
1061static __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(set: pw->p[i].set);
1070 FN(EL,free)(qp: 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(set: context);
1077 el = FN(PW,take_base_at)(pw, pos: 0);
1078 el = FN(EL,gist)(qp: el, context);
1079 pw = FN(PW,restore_base_at)(pw, pos: 0, el);
1080 context = isl_set_universe(space);
1081 pw = FN(PW,restore_domain_at)(pw, pos: 0, domain: 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 */
1098static __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_basic_set *bset),
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 isl_basic_set *hull = NULL;
1108
1109 pw = FN(PW,sort_unique)(pw);
1110 if (!pw || !context)
1111 goto error;
1112
1113 if (pw->n == 0) {
1114 isl_set_free(set: context);
1115 return pw;
1116 }
1117
1118 is_universe = isl_set_plain_is_universe(set: context);
1119 if (is_universe < 0)
1120 goto error;
1121 if (is_universe) {
1122 isl_set_free(set: context);
1123 return pw;
1124 }
1125
1126 FN(PW,align_params_set)(obj1: &pw, obj2: &context);
1127
1128 pw = FN(PW,cow)(pw);
1129 if (!pw)
1130 goto error;
1131
1132 if (pw->n == 1) {
1133 int equal;
1134
1135 equal = isl_set_plain_is_equal(set1: pw->p[0].set, set2: context);
1136 if (equal < 0)
1137 goto error;
1138 if (equal)
1139 return FN(PW,gist_last)(pw, context);
1140 }
1141
1142 context = isl_set_compute_divs(set: context);
1143 hull = isl_set_simple_hull(set: isl_set_copy(set: context));
1144
1145 for (i = pw->n - 1; i >= 0; --i) {
1146 isl_set *set_i;
1147 EL *el;
1148 int empty;
1149
1150 if (i == pw->n - 1) {
1151 int equal;
1152 equal = isl_set_plain_is_equal(set1: pw->p[i].set, set2: context);
1153 if (equal < 0)
1154 goto error;
1155 if (equal) {
1156 isl_basic_set_free(bset: hull);
1157 return FN(PW,gist_last)(pw, context);
1158 }
1159 }
1160 set_i = FN(PW,get_domain_at)(pw, pos: i);
1161 set_i = intersect_context(set_i, isl_set_copy(set: context));
1162 empty = isl_set_plain_is_empty(set: set_i);
1163 el = FN(PW,take_base_at)(pw, pos: i);
1164 el = FN(EL,gist)(qp: el, context: set_i);
1165 pw = FN(PW,restore_base_at)(pw, pos: i, el);
1166 set_i = FN(PW,take_domain_at)(pw, pos: i);
1167 set_i = fn_dom(set_i, isl_basic_set_copy(bset: hull));
1168 pw = FN(PW,restore_domain_at)(pw, pos: i, domain: set_i);
1169 if (empty < 0 || !pw)
1170 goto error;
1171 if (empty) {
1172 isl_set_free(set: pw->p[i].set);
1173 FN(EL,free)(qp: pw->p[i].FIELD);
1174 if (i != pw->n - 1)
1175 pw->p[i] = pw->p[pw->n - 1];
1176 pw->n--;
1177 }
1178 }
1179
1180 isl_basic_set_free(bset: hull);
1181 isl_set_free(set: context);
1182
1183 return pw;
1184error:
1185 FN(PW,free)(pw);
1186 isl_basic_set_free(bset: hull);
1187 isl_set_free(set: context);
1188 return NULL;
1189}
1190
1191__isl_give PW *FN(PW,gist)(__isl_take PW *pw, __isl_take isl_set *context)
1192{
1193 return FN(PW,gist_fn)(pw, context, fn_dom: &isl_set_gist_basic_set,
1194 intersect_context: &isl_set_intersect);
1195}
1196
1197__isl_give PW *FN(PW,gist_params)(__isl_take PW *pw,
1198 __isl_take isl_set *context)
1199{
1200 return FN(PW,gist_fn)(pw, context, fn_dom: &isl_set_gist_params_basic_set,
1201 intersect_context: &isl_set_intersect_params);
1202}
1203
1204/* Coalesce the domains of "pw".
1205 *
1206 * Prior to the actual coalescing, first sort the pieces such that
1207 * pieces with the same function value expression are combined
1208 * into a single piece, the combined domain of which can then
1209 * be coalesced.
1210 */
1211__isl_give PW *FN(PW,coalesce)(__isl_take PW *pw)
1212{
1213 int i;
1214 isl_size n;
1215
1216 pw = FN(PW,sort_unique)(pw);
1217 n = FN(PW,n_piece)(pwqp: pw);
1218 if (n < 0)
1219 return FN(PW,free)(pw);
1220
1221 for (i = 0; i < n; ++i) {
1222 pw->p[i].set = isl_set_coalesce(set: pw->p[i].set);
1223 if (!pw->p[i].set)
1224 goto error;
1225 }
1226
1227 return pw;
1228error:
1229 FN(PW,free)(pw);
1230 return NULL;
1231}
1232
1233isl_ctx *FN(PW,get_ctx)(__isl_keep PW *pw)
1234{
1235 return pw ? isl_space_get_ctx(space: pw->dim) : NULL;
1236}
1237
1238isl_bool FN(PW,involves_dims)(__isl_keep PW *pw, enum isl_dim_type type,
1239 unsigned first, unsigned n)
1240{
1241 int i;
1242 enum isl_dim_type set_type;
1243
1244 if (!pw)
1245 return isl_bool_error;
1246 if (pw->n == 0 || n == 0)
1247 return isl_bool_false;
1248
1249 set_type = type == isl_dim_in ? isl_dim_set : type;
1250
1251 for (i = 0; i < pw->n; ++i) {
1252 isl_bool involves = FN(EL,involves_dims)(qp: pw->p[i].FIELD,
1253 type, first, n);
1254 if (involves < 0 || involves)
1255 return involves;
1256 involves = isl_set_involves_dims(set: pw->p[i].set,
1257 type: set_type, first, n);
1258 if (involves < 0 || involves)
1259 return involves;
1260 }
1261 return isl_bool_false;
1262}
1263
1264__isl_give PW *FN(PW,set_dim_name)(__isl_take PW *pw,
1265 enum isl_dim_type type, unsigned pos, const char *s)
1266{
1267 isl_space *space;
1268
1269 space = FN(PW,get_space)(pw);
1270 space = isl_space_set_dim_name(space, type, pos, name: s);
1271 return FN(PW,reset_space)(pwqp: pw, space);
1272}
1273
1274__isl_give PW *FN(PW,drop_dims)(__isl_take PW *pw,
1275 enum isl_dim_type type, unsigned first, unsigned n)
1276{
1277 int i;
1278 isl_size n_piece;
1279 enum isl_dim_type set_type;
1280 isl_space *space;
1281
1282 n_piece = FN(PW,n_piece)(pwqp: pw);
1283 if (n_piece < 0)
1284 return FN(PW,free)(pw);
1285 if (n == 0 && !isl_space_get_tuple_name(space: pw->dim, type))
1286 return pw;
1287
1288 set_type = type == isl_dim_in ? isl_dim_set : type;
1289
1290 space = FN(PW,take_space)(pw);
1291 space = isl_space_drop_dims(space, type, first, num: n);
1292 pw = FN(PW,restore_space)(pw, space);
1293 for (i = 0; i < n_piece; ++i) {
1294 isl_set *domain;
1295 EL *el;
1296
1297 el = FN(PW,take_base_at)(pw, pos: i);
1298 el = FN(EL,drop_dims)(qp: el, type, first, n);
1299 pw = FN(PW,restore_base_at)(pw, pos: i, el);
1300 if (type == isl_dim_out)
1301 continue;
1302 domain = FN(PW,take_domain_at)(pw, pos: i);
1303 domain = isl_set_drop(set: domain, type: set_type, first, n);
1304 pw = FN(PW,restore_domain_at)(pw, pos: i, domain);
1305 }
1306
1307 return pw;
1308}
1309
1310/* This function is very similar to drop_dims.
1311 * The only difference is that the cells may still involve
1312 * the specified dimensions. They are removed using
1313 * isl_set_project_out instead of isl_set_drop.
1314 */
1315__isl_give PW *FN(PW,project_out)(__isl_take PW *pw,
1316 enum isl_dim_type type, unsigned first, unsigned n)
1317{
1318 int i;
1319 isl_size n_piece;
1320 enum isl_dim_type set_type;
1321 isl_space *space;
1322
1323 n_piece = FN(PW,n_piece)(pwqp: pw);
1324 if (n_piece < 0)
1325 return FN(PW,free)(pw);
1326 if (n == 0 && !isl_space_get_tuple_name(space: pw->dim, type))
1327 return pw;
1328
1329 set_type = type == isl_dim_in ? isl_dim_set : type;
1330
1331 space = FN(PW,take_space)(pw);
1332 space = isl_space_drop_dims(space, type, first, num: n);
1333 pw = FN(PW,restore_space)(pw, space);
1334 for (i = 0; i < n_piece; ++i) {
1335 isl_set *domain;
1336 EL *el;
1337
1338 domain = FN(PW,take_domain_at)(pw, pos: i);
1339 domain = isl_set_project_out(set: domain, type: set_type, first, n);
1340 pw = FN(PW,restore_domain_at)(pw, pos: i, domain);
1341 el = FN(PW,take_base_at)(pw, pos: i);
1342 el = FN(EL,drop_dims)(qp: el, type, first, n);
1343 pw = FN(PW,restore_base_at)(pw, pos: i, el);
1344 }
1345
1346 return pw;
1347}
1348
1349/* Project the domain of pw onto its parameter space.
1350 */
1351__isl_give PW *FN(PW,project_domain_on_params)(__isl_take PW *pw)
1352{
1353 isl_space *space;
1354 isl_size n;
1355
1356 n = FN(PW,dim)(pwqp: pw, type: isl_dim_in);
1357 if (n < 0)
1358 return FN(PW,free)(pw);
1359 pw = FN(PW,project_out)(pw, type: isl_dim_in, first: 0, n);
1360 space = FN(PW,get_domain_space)(pwqp: pw);
1361 space = isl_space_params(space);
1362 pw = FN(PW,reset_domain_space)(pwqp: pw, space);
1363 return pw;
1364}
1365
1366/* Drop all parameters not referenced by "pw".
1367 */
1368__isl_give PW *FN(PW,drop_unused_params)(__isl_take PW *pw)
1369{
1370 isl_size n;
1371 int i;
1372
1373 if (FN(PW,check_named_params)(obj: pw) < 0)
1374 return FN(PW,free)(pw);
1375
1376 n = FN(PW,dim)(pwqp: pw, type: isl_dim_param);
1377 if (n < 0)
1378 return FN(PW,free)(pw);
1379 for (i = n - 1; i >= 0; i--) {
1380 isl_bool involves;
1381
1382 involves = FN(PW,involves_dims)(pw, type: isl_dim_param, first: i, n: 1);
1383 if (involves < 0)
1384 return FN(PW,free)(pw);
1385 if (!involves)
1386 pw = FN(PW,drop_dims)(pw, type: isl_dim_param, first: i, n: 1);
1387 }
1388
1389 return pw;
1390}
1391
1392isl_size FN(PW,dim)(__isl_keep PW *pw, enum isl_dim_type type)
1393{
1394 return isl_space_dim(FN(PW,peek_space)(pw), type);
1395}
1396
1397__isl_give isl_space *FN(PW,get_domain_space)(__isl_keep PW *pw)
1398{
1399 return pw ? isl_space_domain(space: isl_space_copy(space: pw->dim)) : NULL;
1400}
1401
1402/* Return the position of the dimension of the given type and name
1403 * in "pw".
1404 * Return -1 if no such dimension can be found.
1405 */
1406int FN(PW,find_dim_by_name)(__isl_keep PW *pw,
1407 enum isl_dim_type type, const char *name)
1408{
1409 if (!pw)
1410 return -1;
1411 return isl_space_find_dim_by_name(space: pw->dim, type, name);
1412}
1413
1414/* Return the position of the dimension of the given type and identifier
1415 * in "pw".
1416 * Return -1 if no such dimension can be found.
1417 */
1418static int FN(PW,find_dim_by_id)(__isl_keep PW *pw,
1419 enum isl_dim_type type, __isl_keep isl_id *id)
1420{
1421 isl_space *space;
1422
1423 space = FN(PW,peek_space)(pw);
1424 return isl_space_find_dim_by_id(space, type, id);
1425}
1426
1427/* Does the piecewise expression "pw" depend in any way
1428 * on the parameter with identifier "id"?
1429 */
1430isl_bool FN(PW,involves_param_id)(__isl_keep PW *pw, __isl_keep isl_id *id)
1431{
1432 int pos;
1433
1434 if (!pw || !id)
1435 return isl_bool_error;
1436 if (pw->n == 0)
1437 return isl_bool_false;
1438
1439 pos = FN(PW,find_dim_by_id)(pw, type: isl_dim_param, id);
1440 if (pos < 0)
1441 return isl_bool_false;
1442 return FN(PW,involves_dims)(pw, type: isl_dim_param, first: pos, n: 1);
1443}
1444
1445/* Reset the space of "pw". Since we don't know if the elements
1446 * represent the spaces themselves or their domains, we pass along
1447 * both when we call their reset_space_and_domain.
1448 */
1449static __isl_give PW *FN(PW,reset_space_and_domain)(__isl_take PW *pw,
1450 __isl_take isl_space *space, __isl_take isl_space *domain)
1451{
1452 int i;
1453 isl_size n;
1454
1455 n = FN(PW,n_piece)(pwqp: pw);
1456 if (n < 0 || !space || !domain)
1457 goto error;
1458
1459 for (i = 0; i < n; ++i) {
1460 isl_set *set;
1461 EL *el;
1462
1463 set = FN(PW,take_domain_at)(pw, pos: i);
1464 set = isl_set_reset_space(set, space: isl_space_copy(space: domain));
1465 pw = FN(PW,restore_domain_at)(pw, pos: i, domain: set);
1466 el = FN(PW,take_base_at)(pw, pos: i);
1467 el = FN(EL,reset_space_and_domain)(qp: el,
1468 space: isl_space_copy(space), domain: isl_space_copy(space: domain));
1469 pw = FN(PW,restore_base_at)(pw, pos: i, el);
1470 }
1471
1472 isl_space_free(space: domain);
1473
1474 pw = FN(PW,restore_space)(pw, space);
1475
1476 return pw;
1477error:
1478 isl_space_free(space: domain);
1479 isl_space_free(space);
1480 FN(PW,free)(pw);
1481 return NULL;
1482}
1483
1484__isl_give PW *FN(PW,reset_domain_space)(__isl_take PW *pw,
1485 __isl_take isl_space *domain)
1486{
1487 isl_space *space;
1488
1489 space = isl_space_extend_domain_with_range(domain: isl_space_copy(space: domain),
1490 FN(PW,get_space)(pw));
1491 return FN(PW,reset_space_and_domain)(pw, space, domain);
1492}
1493
1494__isl_give PW *FN(PW,reset_space)(__isl_take PW *pw,
1495 __isl_take isl_space *space)
1496{
1497 isl_space *domain;
1498
1499 domain = isl_space_domain(space: isl_space_copy(space));
1500 return FN(PW,reset_space_and_domain)(pw, space, domain);
1501}
1502
1503__isl_give PW *FN(PW,set_tuple_id)(__isl_take PW *pw, enum isl_dim_type type,
1504 __isl_take isl_id *id)
1505{
1506 isl_space *space;
1507
1508 pw = FN(PW,cow)(pw);
1509 if (!pw)
1510 goto error;
1511
1512 space = FN(PW,get_space)(pw);
1513 space = isl_space_set_tuple_id(space, type, id);
1514
1515 return FN(PW,reset_space)(pw, space);
1516error:
1517 isl_id_free(id);
1518 return FN(PW,free)(pw);
1519}
1520
1521/* Drop the id on the specified tuple.
1522 */
1523__isl_give PW *FN(PW,reset_tuple_id)(__isl_take PW *pw, enum isl_dim_type type)
1524{
1525 isl_space *space;
1526
1527 if (!pw)
1528 return NULL;
1529 if (!FN(PW,has_tuple_id)(pw, type))
1530 return pw;
1531
1532 pw = FN(PW,cow)(pw);
1533 if (!pw)
1534 return NULL;
1535
1536 space = FN(PW,get_space)(pw);
1537 space = isl_space_reset_tuple_id(space, type);
1538
1539 return FN(PW,reset_space)(pw, space);
1540}
1541
1542__isl_give PW *FN(PW,set_dim_id)(__isl_take PW *pw,
1543 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
1544{
1545 isl_space *space;
1546
1547 space = FN(PW,get_space)(pw);
1548 space = isl_space_set_dim_id(space, type, pos, id);
1549 return FN(PW,reset_space)(pw, space);
1550}
1551
1552/* Reset the user pointer on all identifiers of parameters and tuples
1553 * of the space of "pw".
1554 */
1555__isl_give PW *FN(PW,reset_user)(__isl_take PW *pw)
1556{
1557 isl_space *space;
1558
1559 space = FN(PW,get_space)(pw);
1560 space = isl_space_reset_user(space);
1561
1562 return FN(PW,reset_space)(pw, space);
1563}
1564
1565isl_size FN(PW,n_piece)(__isl_keep PW *pw)
1566{
1567 return pw ? pw->n : isl_size_error;
1568}
1569
1570isl_stat FN(PW,foreach_piece)(__isl_keep PW *pw,
1571 isl_stat (*fn)(__isl_take isl_set *set, __isl_take EL *el, void *user),
1572 void *user)
1573{
1574 int i;
1575
1576 if (!pw)
1577 return isl_stat_error;
1578
1579 for (i = 0; i < pw->n; ++i)
1580 if (fn(isl_set_copy(set: pw->p[i].set),
1581 FN(EL,copy)(qp: pw->p[i].FIELD), user) < 0)
1582 return isl_stat_error;
1583
1584 return isl_stat_ok;
1585}
1586
1587/* Does "test" succeed on every cell of "pw"?
1588 */
1589isl_bool FN(PW,every_piece)(__isl_keep PW *pw,
1590 isl_bool (*test)(__isl_keep isl_set *set,
1591 __isl_keep EL *el, void *user), void *user)
1592{
1593 int i;
1594
1595 if (!pw)
1596 return isl_bool_error;
1597
1598 for (i = 0; i < pw->n; ++i) {
1599 isl_bool r;
1600
1601 r = test(pw->p[i].set, pw->p[i].FIELD, user);
1602 if (r < 0 || !r)
1603 return r;
1604 }
1605
1606 return isl_bool_true;
1607}
1608
1609/* Is "pw" defined over a single universe domain?
1610 *
1611 * If the default value of this piecewise type is zero,
1612 * then a "pw" with a zero number of cells is also accepted
1613 * as it represents the default zero value.
1614 */
1615isl_bool FN(FN(PW,isa),BASE)(__isl_keep PW *pw)
1616{
1617 isl_size n;
1618
1619 n = FN(PW,n_piece)(pw);
1620 if (n < 0)
1621 return isl_bool_error;
1622 if (DEFAULT_IS_ZERO && n == 0)
1623 return isl_bool_true;
1624 if (n != 1)
1625 return isl_bool_false;
1626 return isl_set_plain_is_universe(FN(PW,peek_domain_at)(pw, pos: 0));
1627}
1628
1629/* Return a zero base expression in the same space (and of the same type)
1630 * as "pw".
1631 */
1632static __isl_give EL *FN(EL,zero_like_type)(__isl_take PW *pw OPT_TYPE_PARAM)
1633{
1634 isl_space *space;
1635
1636 space = FN(PW,get_space)(pw);
1637 FN(PW,free)(pw);
1638 return FN(EL,zero_in_space)(space OPT_TYPE_ARG(NO_LOC));
1639}
1640
1641#ifndef HAS_TYPE
1642/* Return a zero base expression in the same space as "pw".
1643 */
1644static __isl_give EL *FN(EL,zero_like)(__isl_take PW *pw)
1645{
1646 return FN(EL,zero_like_type)(pw);
1647}
1648#else
1649/* Return a zero base expression in the same space and of the same type
1650 * as "pw".
1651 *
1652 * Pass along the type as an explicit argument for uniform handling
1653 * in isl_*_zero_like_type.
1654 */
1655static __isl_give EL *FN(EL,zero_like)(__isl_take PW *pw)
1656{
1657 enum isl_fold type;
1658
1659 type = FN(PW,get_type)(pw);
1660 if (type < 0)
1661 goto error;
1662 return FN(EL,zero_like_type)(pw, type);
1663error:
1664 FN(PW,free)(pw);
1665 return NULL;
1666}
1667#endif
1668
1669/* Given that "pw" is defined over a single universe domain,
1670 * return the base expression associated to this domain.
1671 *
1672 * If the number of cells is zero, then "pw" is of a piecewise type
1673 * with a default zero value and effectively represents zero.
1674 * In this case, create a zero base expression in the same space
1675 * (and with the same type).
1676 * Otherwise, simply extract the associated base expression.
1677 */
1678__isl_give EL *FN(FN(PW,as),BASE)(__isl_take PW *pw)
1679{
1680 isl_bool is_total;
1681 isl_size n;
1682 EL *el;
1683
1684 is_total = FN(FN(PW,isa),BASE)(pw);
1685 if (is_total < 0)
1686 goto error;
1687 if (!is_total)
1688 isl_die(FN(PW,get_ctx)(pw), isl_error_invalid,
1689 "expecting single total function", goto error);
1690 n = FN(PW,n_piece)(pw);
1691 if (n < 0)
1692 goto error;
1693 if (n == 0)
1694 return FN(EL,zero_like)(pw);
1695 el = FN(PW,take_base_at)(pw, pos: 0);
1696 FN(PW,free)(pw);
1697 return el;
1698error:
1699 FN(PW,free)(pw);
1700 return NULL;
1701}
1702
1703#ifdef HAS_TYPE
1704/* Negate the type of "pw".
1705 */
1706static __isl_give PW *FN(PW,negate_type)(__isl_take PW *pw)
1707{
1708 pw = FN(PW,cow)(pw);
1709 if (!pw)
1710 return NULL;
1711 pw->type = isl_fold_type_negate(pw->type);
1712 return pw;
1713}
1714#else
1715/* Negate the type of "pw".
1716 * Since "pw" does not have a type, do nothing.
1717 */
1718static __isl_give PW *FN(PW,negate_type)(__isl_take PW *pw)
1719{
1720 return pw;
1721}
1722#endif
1723
1724/* Multiply the pieces of "pw" by "v" and return the result.
1725 */
1726__isl_give PW *FN(PW,scale_val)(__isl_take PW *pw, __isl_take isl_val *v)
1727{
1728 int i;
1729 isl_size n;
1730
1731 if (!pw || !v)
1732 goto error;
1733
1734 if (isl_val_is_one(v)) {
1735 isl_val_free(v);
1736 return pw;
1737 }
1738 if (pw && DEFAULT_IS_ZERO && isl_val_is_zero(v)) {
1739 PW *zero;
1740 isl_space *space = FN(PW,get_space)(pw);
1741 zero = FN(PW,ZERO)(space OPT_TYPE_ARG(pw->));
1742 FN(PW,free)(pw);
1743 isl_val_free(v);
1744 return zero;
1745 }
1746 if (isl_val_is_neg(v))
1747 pw = FN(PW,negate_type)(pw);
1748 n = FN(PW,n_piece)(pw);
1749 if (n < 0)
1750 goto error;
1751
1752 for (i = 0; i < n; ++i) {
1753 EL *el;
1754
1755 el = FN(PW,take_base_at)(pw, pos: i);
1756 el = FN(EL,scale_val)(qp: el, v: isl_val_copy(v));
1757 pw = FN(PW,restore_base_at)(pw, pos: i, el);
1758 }
1759
1760 isl_val_free(v);
1761 return pw;
1762error:
1763 isl_val_free(v);
1764 FN(PW,free)(pw);
1765 return NULL;
1766}
1767
1768/* Divide the pieces of "pw" by "v" and return the result.
1769 */
1770__isl_give PW *FN(PW,scale_down_val)(__isl_take PW *pw, __isl_take isl_val *v)
1771{
1772 int i;
1773 isl_size n;
1774
1775 if (!pw || !v)
1776 goto error;
1777
1778 if (isl_val_is_one(v)) {
1779 isl_val_free(v);
1780 return pw;
1781 }
1782
1783 if (!isl_val_is_rat(v))
1784 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1785 "expecting rational factor", goto error);
1786 if (isl_val_is_zero(v))
1787 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1788 "cannot scale down by zero", goto error);
1789
1790 if (isl_val_is_neg(v))
1791 pw = FN(PW,negate_type)(pw);
1792 n = FN(PW,n_piece)(pw);
1793 if (n < 0)
1794 goto error;
1795
1796 for (i = 0; i < n; ++i) {
1797 EL *el;
1798
1799 el = FN(PW,take_base_at)(pw, pos: i);
1800 el = FN(EL,scale_down_val)(qp: el, v: isl_val_copy(v));
1801 pw = FN(PW,restore_base_at)(pw, pos: i, el);
1802 }
1803
1804 isl_val_free(v);
1805 return pw;
1806error:
1807 isl_val_free(v);
1808 FN(PW,free)(pw);
1809 return NULL;
1810}
1811
1812/* Apply some normalization to "pw".
1813 * In particular, sort the pieces according to their function value
1814 * expressions, combining pairs of adjacent pieces with
1815 * the same such expression, and then normalize the domains of the pieces.
1816 *
1817 * We normalize in place, but if anything goes wrong we need
1818 * to return NULL, so we need to make sure we don't change the
1819 * meaning of any possible other copies of "pw".
1820 */
1821static __isl_give PW *FN(PW,normalize)(__isl_take PW *pw)
1822{
1823 int i;
1824 isl_set *set;
1825
1826 pw = FN(PW,sort_unique)(pw);
1827 if (!pw)
1828 return NULL;
1829 for (i = 0; i < pw->n; ++i) {
1830 set = isl_set_normalize(set: isl_set_copy(set: pw->p[i].set));
1831 if (!set)
1832 return FN(PW,free)(pw);
1833 isl_set_free(set: pw->p[i].set);
1834 pw->p[i].set = set;
1835 }
1836
1837 return pw;
1838}
1839
1840/* Is pw1 obviously equal to pw2?
1841 * That is, do they have obviously identical cells and obviously identical
1842 * elements on each cell?
1843 *
1844 * If "pw1" or "pw2" contain any NaNs, then they are considered
1845 * not to be the same. A NaN is not equal to anything, not even
1846 * to another NaN.
1847 */
1848isl_bool FN(PW,plain_is_equal)(__isl_keep PW *pw1, __isl_keep PW *pw2)
1849{
1850 int i;
1851 isl_bool equal, has_nan;
1852
1853 if (!pw1 || !pw2)
1854 return isl_bool_error;
1855
1856 has_nan = FN(PW,involves_nan)(pwqp: pw1);
1857 if (has_nan >= 0 && !has_nan)
1858 has_nan = FN(PW,involves_nan)(pwqp: pw2);
1859 if (has_nan < 0 || has_nan)
1860 return isl_bool_not(b: has_nan);
1861
1862 if (pw1 == pw2)
1863 return isl_bool_true;
1864 equal = FN(PW,has_equal_space)(obj1: pw1, obj2: pw2);
1865 if (equal < 0 || !equal)
1866 return equal;
1867
1868 pw1 = FN(PW,copy)(pw: pw1);
1869 pw2 = FN(PW,copy)(pw: pw2);
1870 pw1 = FN(PW,normalize)(pw: pw1);
1871 pw2 = FN(PW,normalize)(pw: pw2);
1872 if (!pw1 || !pw2)
1873 goto error;
1874
1875 equal = isl_bool_ok(b: pw1->n == pw2->n);
1876 for (i = 0; equal && i < pw1->n; ++i) {
1877 equal = isl_set_plain_is_equal(set1: pw1->p[i].set, set2: pw2->p[i].set);
1878 if (equal < 0)
1879 goto error;
1880 if (!equal)
1881 break;
1882 equal = FN(EL,plain_is_equal)(qp1: pw1->p[i].FIELD, qp2: pw2->p[i].FIELD);
1883 if (equal < 0)
1884 goto error;
1885 }
1886
1887 FN(PW,free)(pw: pw1);
1888 FN(PW,free)(pw: pw2);
1889 return equal;
1890error:
1891 FN(PW,free)(pw: pw1);
1892 FN(PW,free)(pw: pw2);
1893 return isl_bool_error;
1894}
1895
1896/* Does "pw" involve any NaNs?
1897 */
1898isl_bool FN(PW,involves_nan)(__isl_keep PW *pw)
1899{
1900 int i;
1901
1902 if (!pw)
1903 return isl_bool_error;
1904 if (pw->n == 0)
1905 return isl_bool_false;
1906
1907 for (i = 0; i < pw->n; ++i) {
1908 isl_bool has_nan = FN(EL,involves_nan)(qp: pw->p[i].FIELD);
1909 if (has_nan < 0 || has_nan)
1910 return has_nan;
1911 }
1912
1913 return isl_bool_false;
1914}
1915

source code of polly/lib/External/isl/isl_pw_templ.c