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