xref: /netbsd-src/external/mit/isl/dist/isl_pw_templ.c (revision 5971e316fdea024efff6be8f03536623db06833e)
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