Line data Source code
1 : /*
2 : * Copyright 2010 INRIA Saclay
3 : *
4 : * Use of this software is governed by the MIT license
5 : *
6 : * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7 : * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
8 : * 91893 Orsay, France
9 : */
10 :
11 : #include <isl_map_private.h>
12 : #include <isl_union_map_private.h>
13 : #include <isl_polynomial_private.h>
14 : #include <isl_point_private.h>
15 : #include <isl_space_private.h>
16 : #include <isl_lp_private.h>
17 : #include <isl_seq.h>
18 : #include <isl_mat_private.h>
19 : #include <isl_val_private.h>
20 : #include <isl_vec_private.h>
21 : #include <isl_config.h>
22 :
23 : #undef BASE
24 : #define BASE pw_qpolynomial_fold
25 :
26 : #include <isl_list_templ.c>
27 :
28 0 : enum isl_fold isl_fold_type_negate(enum isl_fold type)
29 : {
30 0 : switch (type) {
31 : case isl_fold_min:
32 0 : return isl_fold_max;
33 : case isl_fold_max:
34 0 : return isl_fold_min;
35 : case isl_fold_list:
36 0 : return isl_fold_list;
37 : }
38 :
39 0 : isl_die(NULL, isl_error_internal, "unhandled isl_fold type", abort());
40 : }
41 :
42 0 : static __isl_give isl_qpolynomial_fold *qpolynomial_fold_alloc(
43 : enum isl_fold type, __isl_take isl_space *dim, int n)
44 : {
45 : isl_qpolynomial_fold *fold;
46 :
47 0 : if (!dim)
48 0 : goto error;
49 :
50 0 : isl_assert(dim->ctx, n >= 0, goto error);
51 0 : fold = isl_calloc(dim->ctx, struct isl_qpolynomial_fold,
52 : sizeof(struct isl_qpolynomial_fold) +
53 : (n - 1) * sizeof(struct isl_qpolynomial *));
54 0 : if (!fold)
55 0 : goto error;
56 :
57 0 : fold->ref = 1;
58 0 : fold->size = n;
59 0 : fold->n = 0;
60 0 : fold->type = type;
61 0 : fold->dim = dim;
62 :
63 0 : return fold;
64 : error:
65 0 : isl_space_free(dim);
66 0 : return NULL;
67 : }
68 :
69 0 : isl_ctx *isl_qpolynomial_fold_get_ctx(__isl_keep isl_qpolynomial_fold *fold)
70 : {
71 0 : return fold ? fold->dim->ctx : NULL;
72 : }
73 :
74 0 : __isl_give isl_space *isl_qpolynomial_fold_get_domain_space(
75 : __isl_keep isl_qpolynomial_fold *fold)
76 : {
77 0 : return fold ? isl_space_copy(fold->dim) : NULL;
78 : }
79 :
80 0 : __isl_give isl_space *isl_qpolynomial_fold_get_space(
81 : __isl_keep isl_qpolynomial_fold *fold)
82 : {
83 : isl_space *space;
84 0 : if (!fold)
85 0 : return NULL;
86 0 : space = isl_space_copy(fold->dim);
87 0 : space = isl_space_from_domain(space);
88 0 : space = isl_space_add_dims(space, isl_dim_out, 1);
89 0 : return space;
90 : }
91 :
92 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_reset_domain_space(
93 : __isl_take isl_qpolynomial_fold *fold, __isl_take isl_space *dim)
94 : {
95 : int i;
96 :
97 0 : fold = isl_qpolynomial_fold_cow(fold);
98 0 : if (!fold || !dim)
99 : goto error;
100 :
101 0 : for (i = 0; i < fold->n; ++i) {
102 0 : fold->qp[i] = isl_qpolynomial_reset_domain_space(fold->qp[i],
103 : isl_space_copy(dim));
104 0 : if (!fold->qp[i])
105 0 : goto error;
106 : }
107 :
108 0 : isl_space_free(fold->dim);
109 0 : fold->dim = dim;
110 :
111 0 : return fold;
112 : error:
113 0 : isl_qpolynomial_fold_free(fold);
114 0 : isl_space_free(dim);
115 0 : return NULL;
116 : }
117 :
118 : /* Reset the space of "fold". This function is called from isl_pw_templ.c
119 : * and doesn't know if the space of an element object is represented
120 : * directly or through its domain. It therefore passes along both.
121 : */
122 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_reset_space_and_domain(
123 : __isl_take isl_qpolynomial_fold *fold, __isl_take isl_space *space,
124 : __isl_take isl_space *domain)
125 : {
126 0 : isl_space_free(space);
127 0 : return isl_qpolynomial_fold_reset_domain_space(fold, domain);
128 : }
129 :
130 0 : int isl_qpolynomial_fold_involves_dims(__isl_keep isl_qpolynomial_fold *fold,
131 : enum isl_dim_type type, unsigned first, unsigned n)
132 : {
133 : int i;
134 :
135 0 : if (!fold)
136 0 : return -1;
137 0 : if (fold->n == 0 || n == 0)
138 0 : return 0;
139 :
140 0 : for (i = 0; i < fold->n; ++i) {
141 0 : int involves = isl_qpolynomial_involves_dims(fold->qp[i],
142 : type, first, n);
143 0 : if (involves < 0 || involves)
144 0 : return involves;
145 : }
146 0 : return 0;
147 : }
148 :
149 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_set_dim_name(
150 : __isl_take isl_qpolynomial_fold *fold,
151 : enum isl_dim_type type, unsigned pos, const char *s)
152 : {
153 : int i;
154 :
155 0 : fold = isl_qpolynomial_fold_cow(fold);
156 0 : if (!fold)
157 0 : return NULL;
158 0 : fold->dim = isl_space_set_dim_name(fold->dim, type, pos, s);
159 0 : if (!fold->dim)
160 0 : goto error;
161 :
162 0 : for (i = 0; i < fold->n; ++i) {
163 0 : fold->qp[i] = isl_qpolynomial_set_dim_name(fold->qp[i],
164 : type, pos, s);
165 0 : if (!fold->qp[i])
166 0 : goto error;
167 : }
168 :
169 0 : return fold;
170 : error:
171 0 : isl_qpolynomial_fold_free(fold);
172 0 : return NULL;
173 : }
174 :
175 : /* Given a dimension type for an isl_qpolynomial_fold,
176 : * return the corresponding type for the domain.
177 : */
178 0 : static enum isl_dim_type domain_type(enum isl_dim_type type)
179 : {
180 0 : if (type == isl_dim_in)
181 0 : return isl_dim_set;
182 0 : return type;
183 : }
184 :
185 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_drop_dims(
186 : __isl_take isl_qpolynomial_fold *fold,
187 : enum isl_dim_type type, unsigned first, unsigned n)
188 : {
189 : int i;
190 : enum isl_dim_type set_type;
191 :
192 0 : if (!fold)
193 0 : return NULL;
194 0 : if (n == 0)
195 0 : return fold;
196 :
197 0 : set_type = domain_type(type);
198 :
199 0 : fold = isl_qpolynomial_fold_cow(fold);
200 0 : if (!fold)
201 0 : return NULL;
202 0 : fold->dim = isl_space_drop_dims(fold->dim, set_type, first, n);
203 0 : if (!fold->dim)
204 0 : goto error;
205 :
206 0 : for (i = 0; i < fold->n; ++i) {
207 0 : fold->qp[i] = isl_qpolynomial_drop_dims(fold->qp[i],
208 : type, first, n);
209 0 : if (!fold->qp[i])
210 0 : goto error;
211 : }
212 :
213 0 : return fold;
214 : error:
215 0 : isl_qpolynomial_fold_free(fold);
216 0 : return NULL;
217 : }
218 :
219 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_insert_dims(
220 : __isl_take isl_qpolynomial_fold *fold,
221 : enum isl_dim_type type, unsigned first, unsigned n)
222 : {
223 : int i;
224 :
225 0 : if (!fold)
226 0 : return NULL;
227 0 : if (n == 0 && !isl_space_is_named_or_nested(fold->dim, type))
228 0 : return fold;
229 :
230 0 : fold = isl_qpolynomial_fold_cow(fold);
231 0 : if (!fold)
232 0 : return NULL;
233 0 : fold->dim = isl_space_insert_dims(fold->dim, type, first, n);
234 0 : if (!fold->dim)
235 0 : goto error;
236 :
237 0 : for (i = 0; i < fold->n; ++i) {
238 0 : fold->qp[i] = isl_qpolynomial_insert_dims(fold->qp[i],
239 : type, first, n);
240 0 : if (!fold->qp[i])
241 0 : goto error;
242 : }
243 :
244 0 : return fold;
245 : error:
246 0 : isl_qpolynomial_fold_free(fold);
247 0 : return NULL;
248 : }
249 :
250 : /* Determine the sign of the constant quasipolynomial "qp".
251 : *
252 : * Return
253 : * -1 if qp <= 0
254 : * 1 if qp >= 0
255 : * 0 if unknown
256 : *
257 : * For qp == 0, we can return either -1 or 1. In practice, we return 1.
258 : * For qp == NaN, the sign is undefined, so we return 0.
259 : */
260 0 : static int isl_qpolynomial_cst_sign(__isl_keep isl_qpolynomial *qp)
261 : {
262 : struct isl_upoly_cst *cst;
263 :
264 0 : if (isl_qpolynomial_is_nan(qp))
265 0 : return 0;
266 :
267 0 : cst = isl_upoly_as_cst(qp->upoly);
268 0 : if (!cst)
269 0 : return 0;
270 :
271 0 : return isl_int_sgn(cst->n) < 0 ? -1 : 1;
272 : }
273 :
274 0 : static int isl_qpolynomial_aff_sign(__isl_keep isl_set *set,
275 : __isl_keep isl_qpolynomial *qp)
276 : {
277 : enum isl_lp_result res;
278 : isl_vec *aff;
279 : isl_int opt;
280 0 : int sgn = 0;
281 :
282 0 : aff = isl_qpolynomial_extract_affine(qp);
283 0 : if (!aff)
284 0 : return 0;
285 :
286 0 : isl_int_init(opt);
287 :
288 0 : res = isl_set_solve_lp(set, 0, aff->el + 1, aff->el[0],
289 : &opt, NULL, NULL);
290 0 : if (res == isl_lp_error)
291 0 : goto done;
292 0 : if (res == isl_lp_empty ||
293 0 : (res == isl_lp_ok && !isl_int_is_neg(opt))) {
294 0 : sgn = 1;
295 0 : goto done;
296 : }
297 :
298 0 : res = isl_set_solve_lp(set, 1, aff->el + 1, aff->el[0],
299 : &opt, NULL, NULL);
300 0 : if (res == isl_lp_ok && !isl_int_is_pos(opt))
301 0 : sgn = -1;
302 :
303 : done:
304 0 : isl_int_clear(opt);
305 0 : isl_vec_free(aff);
306 0 : return sgn;
307 : }
308 :
309 : /* Determine, if possible, the sign of the quasipolynomial "qp" on
310 : * the domain "set".
311 : *
312 : * If qp is a constant, then the problem is trivial.
313 : * If qp is linear, then we check if the minimum of the corresponding
314 : * affine constraint is non-negative or if the maximum is non-positive.
315 : *
316 : * Otherwise, we check if the outermost variable "v" has a lower bound "l"
317 : * in "set". If so, we write qp(v,v') as
318 : *
319 : * q(v,v') * (v - l) + r(v')
320 : *
321 : * if q(v,v') and r(v') have the same known sign, then the original
322 : * quasipolynomial has the same sign as well.
323 : *
324 : * Return
325 : * -1 if qp <= 0
326 : * 1 if qp >= 0
327 : * 0 if unknown
328 : */
329 0 : static int isl_qpolynomial_sign(__isl_keep isl_set *set,
330 : __isl_keep isl_qpolynomial *qp)
331 : {
332 : int d;
333 : int i;
334 : int is;
335 : struct isl_upoly_rec *rec;
336 : isl_vec *v;
337 : isl_int l;
338 : enum isl_lp_result res;
339 0 : int sgn = 0;
340 :
341 0 : is = isl_qpolynomial_is_cst(qp, NULL, NULL);
342 0 : if (is < 0)
343 0 : return 0;
344 0 : if (is)
345 0 : return isl_qpolynomial_cst_sign(qp);
346 :
347 0 : is = isl_qpolynomial_is_affine(qp);
348 0 : if (is < 0)
349 0 : return 0;
350 0 : if (is)
351 0 : return isl_qpolynomial_aff_sign(set, qp);
352 :
353 0 : if (qp->div->n_row > 0)
354 0 : return 0;
355 :
356 0 : rec = isl_upoly_as_rec(qp->upoly);
357 0 : if (!rec)
358 0 : return 0;
359 :
360 0 : d = isl_space_dim(qp->dim, isl_dim_all);
361 0 : v = isl_vec_alloc(set->ctx, 2 + d);
362 0 : if (!v)
363 0 : return 0;
364 :
365 0 : isl_seq_clr(v->el + 1, 1 + d);
366 0 : isl_int_set_si(v->el[0], 1);
367 0 : isl_int_set_si(v->el[2 + qp->upoly->var], 1);
368 :
369 0 : isl_int_init(l);
370 :
371 0 : res = isl_set_solve_lp(set, 0, v->el + 1, v->el[0], &l, NULL, NULL);
372 0 : if (res == isl_lp_ok) {
373 : isl_qpolynomial *min;
374 : isl_qpolynomial *base;
375 : isl_qpolynomial *r, *q;
376 : isl_qpolynomial *t;
377 :
378 0 : min = isl_qpolynomial_cst_on_domain(isl_space_copy(qp->dim), l);
379 0 : base = isl_qpolynomial_var_pow_on_domain(isl_space_copy(qp->dim),
380 0 : qp->upoly->var, 1);
381 :
382 0 : r = isl_qpolynomial_alloc(isl_space_copy(qp->dim), 0,
383 0 : isl_upoly_copy(rec->p[rec->n - 1]));
384 0 : q = isl_qpolynomial_copy(r);
385 :
386 0 : for (i = rec->n - 2; i >= 0; --i) {
387 0 : r = isl_qpolynomial_mul(r, isl_qpolynomial_copy(min));
388 0 : t = isl_qpolynomial_alloc(isl_space_copy(qp->dim), 0,
389 : isl_upoly_copy(rec->p[i]));
390 0 : r = isl_qpolynomial_add(r, t);
391 0 : if (i == 0)
392 0 : break;
393 0 : q = isl_qpolynomial_mul(q, isl_qpolynomial_copy(base));
394 0 : q = isl_qpolynomial_add(q, isl_qpolynomial_copy(r));
395 : }
396 :
397 0 : if (isl_qpolynomial_is_zero(q))
398 0 : sgn = isl_qpolynomial_sign(set, r);
399 0 : else if (isl_qpolynomial_is_zero(r))
400 0 : sgn = isl_qpolynomial_sign(set, q);
401 : else {
402 : int sgn_q, sgn_r;
403 0 : sgn_r = isl_qpolynomial_sign(set, r);
404 0 : sgn_q = isl_qpolynomial_sign(set, q);
405 0 : if (sgn_r == sgn_q)
406 0 : sgn = sgn_r;
407 : }
408 :
409 0 : isl_qpolynomial_free(min);
410 0 : isl_qpolynomial_free(base);
411 0 : isl_qpolynomial_free(q);
412 0 : isl_qpolynomial_free(r);
413 : }
414 :
415 0 : isl_int_clear(l);
416 :
417 0 : isl_vec_free(v);
418 :
419 0 : return sgn;
420 : }
421 :
422 : /* Combine "fold1" and "fold2" into a single reduction, eliminating
423 : * those elements of one reduction that are already covered by the other
424 : * reduction on "set".
425 : *
426 : * If "fold1" or "fold2" is an empty reduction, then return
427 : * the other reduction.
428 : * If "fold1" or "fold2" is a NaN, then return this NaN.
429 : */
430 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold_on_domain(
431 : __isl_keep isl_set *set,
432 : __isl_take isl_qpolynomial_fold *fold1,
433 : __isl_take isl_qpolynomial_fold *fold2)
434 : {
435 : int i, j;
436 : int n1;
437 0 : struct isl_qpolynomial_fold *res = NULL;
438 : int better;
439 :
440 0 : if (!fold1 || !fold2)
441 : goto error;
442 :
443 0 : isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error);
444 0 : isl_assert(fold1->dim->ctx, isl_space_is_equal(fold1->dim, fold2->dim),
445 : goto error);
446 :
447 0 : better = fold1->type == isl_fold_max ? -1 : 1;
448 :
449 0 : if (isl_qpolynomial_fold_is_empty(fold1) ||
450 0 : isl_qpolynomial_fold_is_nan(fold2)) {
451 0 : isl_qpolynomial_fold_free(fold1);
452 0 : return fold2;
453 : }
454 :
455 0 : if (isl_qpolynomial_fold_is_empty(fold2) ||
456 0 : isl_qpolynomial_fold_is_nan(fold1)) {
457 0 : isl_qpolynomial_fold_free(fold2);
458 0 : return fold1;
459 : }
460 :
461 0 : res = qpolynomial_fold_alloc(fold1->type, isl_space_copy(fold1->dim),
462 0 : fold1->n + fold2->n);
463 0 : if (!res)
464 0 : goto error;
465 :
466 0 : for (i = 0; i < fold1->n; ++i) {
467 0 : res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]);
468 0 : if (!res->qp[res->n])
469 0 : goto error;
470 0 : res->n++;
471 : }
472 0 : n1 = res->n;
473 :
474 0 : for (i = 0; i < fold2->n; ++i) {
475 0 : for (j = n1 - 1; j >= 0; --j) {
476 : isl_qpolynomial *d;
477 : int sgn, equal;
478 0 : equal = isl_qpolynomial_plain_is_equal(res->qp[j],
479 0 : fold2->qp[i]);
480 0 : if (equal < 0)
481 0 : goto error;
482 0 : if (equal)
483 0 : break;
484 0 : d = isl_qpolynomial_sub(
485 0 : isl_qpolynomial_copy(res->qp[j]),
486 0 : isl_qpolynomial_copy(fold2->qp[i]));
487 0 : sgn = isl_qpolynomial_sign(set, d);
488 0 : isl_qpolynomial_free(d);
489 0 : if (sgn == 0)
490 0 : continue;
491 0 : if (sgn != better)
492 0 : break;
493 0 : isl_qpolynomial_free(res->qp[j]);
494 0 : if (j != n1 - 1)
495 0 : res->qp[j] = res->qp[n1 - 1];
496 0 : n1--;
497 0 : if (n1 != res->n - 1)
498 0 : res->qp[n1] = res->qp[res->n - 1];
499 0 : res->n--;
500 : }
501 0 : if (j >= 0)
502 0 : continue;
503 0 : res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
504 0 : if (!res->qp[res->n])
505 0 : goto error;
506 0 : res->n++;
507 : }
508 :
509 0 : isl_qpolynomial_fold_free(fold1);
510 0 : isl_qpolynomial_fold_free(fold2);
511 :
512 0 : return res;
513 : error:
514 0 : isl_qpolynomial_fold_free(res);
515 0 : isl_qpolynomial_fold_free(fold1);
516 0 : isl_qpolynomial_fold_free(fold2);
517 0 : return NULL;
518 : }
519 :
520 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_add_qpolynomial(
521 : __isl_take isl_qpolynomial_fold *fold, __isl_take isl_qpolynomial *qp)
522 : {
523 : int i;
524 :
525 0 : if (!fold || !qp)
526 : goto error;
527 :
528 0 : if (isl_qpolynomial_is_zero(qp)) {
529 0 : isl_qpolynomial_free(qp);
530 0 : return fold;
531 : }
532 :
533 0 : fold = isl_qpolynomial_fold_cow(fold);
534 0 : if (!fold)
535 0 : goto error;
536 :
537 0 : for (i = 0; i < fold->n; ++i) {
538 0 : fold->qp[i] = isl_qpolynomial_add(fold->qp[i],
539 : isl_qpolynomial_copy(qp));
540 0 : if (!fold->qp[i])
541 0 : goto error;
542 : }
543 :
544 0 : isl_qpolynomial_free(qp);
545 0 : return fold;
546 : error:
547 0 : isl_qpolynomial_fold_free(fold);
548 0 : isl_qpolynomial_free(qp);
549 0 : return NULL;
550 : }
551 :
552 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_add_on_domain(
553 : __isl_keep isl_set *dom,
554 : __isl_take isl_qpolynomial_fold *fold1,
555 : __isl_take isl_qpolynomial_fold *fold2)
556 : {
557 : int i;
558 0 : isl_qpolynomial_fold *res = NULL;
559 :
560 0 : if (!fold1 || !fold2)
561 : goto error;
562 :
563 0 : if (isl_qpolynomial_fold_is_empty(fold1)) {
564 0 : isl_qpolynomial_fold_free(fold1);
565 0 : return fold2;
566 : }
567 :
568 0 : if (isl_qpolynomial_fold_is_empty(fold2)) {
569 0 : isl_qpolynomial_fold_free(fold2);
570 0 : return fold1;
571 : }
572 :
573 0 : if (fold1->n == 1 && fold2->n != 1)
574 0 : return isl_qpolynomial_fold_add_on_domain(dom, fold2, fold1);
575 :
576 0 : if (fold2->n == 1) {
577 0 : res = isl_qpolynomial_fold_add_qpolynomial(fold1,
578 0 : isl_qpolynomial_copy(fold2->qp[0]));
579 0 : isl_qpolynomial_fold_free(fold2);
580 0 : return res;
581 : }
582 :
583 0 : res = isl_qpolynomial_fold_add_qpolynomial(
584 : isl_qpolynomial_fold_copy(fold1),
585 0 : isl_qpolynomial_copy(fold2->qp[0]));
586 :
587 0 : for (i = 1; i < fold2->n; ++i) {
588 : isl_qpolynomial_fold *res_i;
589 0 : res_i = isl_qpolynomial_fold_add_qpolynomial(
590 : isl_qpolynomial_fold_copy(fold1),
591 0 : isl_qpolynomial_copy(fold2->qp[i]));
592 0 : res = isl_qpolynomial_fold_fold_on_domain(dom, res, res_i);
593 : }
594 :
595 0 : isl_qpolynomial_fold_free(fold1);
596 0 : isl_qpolynomial_fold_free(fold2);
597 0 : return res;
598 : error:
599 0 : isl_qpolynomial_fold_free(res);
600 0 : isl_qpolynomial_fold_free(fold1);
601 0 : isl_qpolynomial_fold_free(fold2);
602 0 : return NULL;
603 : }
604 :
605 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute_equalities(
606 : __isl_take isl_qpolynomial_fold *fold, __isl_take isl_basic_set *eq)
607 : {
608 : int i;
609 :
610 0 : if (!fold || !eq)
611 : goto error;
612 :
613 0 : fold = isl_qpolynomial_fold_cow(fold);
614 0 : if (!fold)
615 0 : return NULL;
616 :
617 0 : for (i = 0; i < fold->n; ++i) {
618 0 : fold->qp[i] = isl_qpolynomial_substitute_equalities(fold->qp[i],
619 : isl_basic_set_copy(eq));
620 0 : if (!fold->qp[i])
621 0 : goto error;
622 : }
623 :
624 0 : isl_basic_set_free(eq);
625 0 : return fold;
626 : error:
627 0 : isl_basic_set_free(eq);
628 0 : isl_qpolynomial_fold_free(fold);
629 0 : return NULL;
630 : }
631 :
632 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_gist(
633 : __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *context)
634 : {
635 : int i;
636 :
637 0 : if (!fold || !context)
638 : goto error;
639 :
640 0 : fold = isl_qpolynomial_fold_cow(fold);
641 0 : if (!fold)
642 0 : return NULL;
643 :
644 0 : for (i = 0; i < fold->n; ++i) {
645 0 : fold->qp[i] = isl_qpolynomial_gist(fold->qp[i],
646 : isl_set_copy(context));
647 0 : if (!fold->qp[i])
648 0 : goto error;
649 : }
650 :
651 0 : isl_set_free(context);
652 0 : return fold;
653 : error:
654 0 : isl_set_free(context);
655 0 : isl_qpolynomial_fold_free(fold);
656 0 : return NULL;
657 : }
658 :
659 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_gist_params(
660 : __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *context)
661 : {
662 0 : isl_space *space = isl_qpolynomial_fold_get_domain_space(fold);
663 0 : isl_set *dom_context = isl_set_universe(space);
664 0 : dom_context = isl_set_intersect_params(dom_context, context);
665 0 : return isl_qpolynomial_fold_gist(fold, dom_context);
666 : }
667 :
668 : #define isl_qpolynomial_fold_involves_nan isl_qpolynomial_fold_is_nan
669 :
670 : #define HAS_TYPE
671 :
672 : #undef PW
673 : #define PW isl_pw_qpolynomial_fold
674 : #undef EL
675 : #define EL isl_qpolynomial_fold
676 : #undef EL_IS_ZERO
677 : #define EL_IS_ZERO is_empty
678 : #undef ZERO
679 : #define ZERO zero
680 : #undef IS_ZERO
681 : #define IS_ZERO is_zero
682 : #undef FIELD
683 : #define FIELD fold
684 : #undef DEFAULT_IS_ZERO
685 : #define DEFAULT_IS_ZERO 1
686 :
687 : #define NO_NEG
688 : #define NO_SUB
689 : #define NO_PULLBACK
690 :
691 : #include <isl_pw_templ.c>
692 : #include <isl_pw_eval.c>
693 :
694 : #undef BASE
695 : #define BASE pw_qpolynomial_fold
696 :
697 : #define NO_SUB
698 :
699 : #include <isl_union_single.c>
700 : #include <isl_union_eval.c>
701 :
702 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_empty(enum isl_fold type,
703 : __isl_take isl_space *dim)
704 : {
705 0 : return qpolynomial_fold_alloc(type, dim, 0);
706 : }
707 :
708 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_alloc(
709 : enum isl_fold type, __isl_take isl_qpolynomial *qp)
710 : {
711 : isl_qpolynomial_fold *fold;
712 :
713 0 : if (!qp)
714 0 : return NULL;
715 :
716 0 : fold = qpolynomial_fold_alloc(type, isl_space_copy(qp->dim), 1);
717 0 : if (!fold)
718 0 : goto error;
719 :
720 0 : fold->qp[0] = qp;
721 0 : fold->n++;
722 :
723 0 : return fold;
724 : error:
725 0 : isl_qpolynomial_fold_free(fold);
726 0 : isl_qpolynomial_free(qp);
727 0 : return NULL;
728 : }
729 :
730 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_copy(
731 : __isl_keep isl_qpolynomial_fold *fold)
732 : {
733 0 : if (!fold)
734 0 : return NULL;
735 :
736 0 : fold->ref++;
737 0 : return fold;
738 : }
739 :
740 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_dup(
741 : __isl_keep isl_qpolynomial_fold *fold)
742 : {
743 : int i;
744 : isl_qpolynomial_fold *dup;
745 :
746 0 : if (!fold)
747 0 : return NULL;
748 0 : dup = qpolynomial_fold_alloc(fold->type,
749 : isl_space_copy(fold->dim), fold->n);
750 0 : if (!dup)
751 0 : return NULL;
752 :
753 0 : dup->n = fold->n;
754 0 : for (i = 0; i < fold->n; ++i) {
755 0 : dup->qp[i] = isl_qpolynomial_copy(fold->qp[i]);
756 0 : if (!dup->qp[i])
757 0 : goto error;
758 : }
759 :
760 0 : return dup;
761 : error:
762 0 : isl_qpolynomial_fold_free(dup);
763 0 : return NULL;
764 : }
765 :
766 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_cow(
767 : __isl_take isl_qpolynomial_fold *fold)
768 : {
769 0 : if (!fold)
770 0 : return NULL;
771 :
772 0 : if (fold->ref == 1)
773 0 : return fold;
774 0 : fold->ref--;
775 0 : return isl_qpolynomial_fold_dup(fold);
776 : }
777 :
778 0 : void isl_qpolynomial_fold_free(__isl_take isl_qpolynomial_fold *fold)
779 : {
780 : int i;
781 :
782 0 : if (!fold)
783 0 : return;
784 0 : if (--fold->ref > 0)
785 0 : return;
786 :
787 0 : for (i = 0; i < fold->n; ++i)
788 0 : isl_qpolynomial_free(fold->qp[i]);
789 0 : isl_space_free(fold->dim);
790 0 : free(fold);
791 : }
792 :
793 0 : int isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold *fold)
794 : {
795 0 : if (!fold)
796 0 : return -1;
797 :
798 0 : return fold->n == 0;
799 : }
800 :
801 : /* Does "fold" represent max(NaN) or min(NaN)?
802 : */
803 0 : isl_bool isl_qpolynomial_fold_is_nan(__isl_keep isl_qpolynomial_fold *fold)
804 : {
805 0 : if (!fold)
806 0 : return isl_bool_error;
807 0 : if (fold->n != 1)
808 0 : return isl_bool_false;
809 0 : return isl_qpolynomial_is_nan(fold->qp[0]);
810 : }
811 :
812 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold(
813 : __isl_take isl_qpolynomial_fold *fold1,
814 : __isl_take isl_qpolynomial_fold *fold2)
815 : {
816 : int i;
817 0 : struct isl_qpolynomial_fold *res = NULL;
818 :
819 0 : if (!fold1 || !fold2)
820 : goto error;
821 :
822 0 : isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error);
823 0 : isl_assert(fold1->dim->ctx, isl_space_is_equal(fold1->dim, fold2->dim),
824 : goto error);
825 :
826 0 : if (isl_qpolynomial_fold_is_empty(fold1)) {
827 0 : isl_qpolynomial_fold_free(fold1);
828 0 : return fold2;
829 : }
830 :
831 0 : if (isl_qpolynomial_fold_is_empty(fold2)) {
832 0 : isl_qpolynomial_fold_free(fold2);
833 0 : return fold1;
834 : }
835 :
836 0 : res = qpolynomial_fold_alloc(fold1->type, isl_space_copy(fold1->dim),
837 0 : fold1->n + fold2->n);
838 0 : if (!res)
839 0 : goto error;
840 :
841 0 : for (i = 0; i < fold1->n; ++i) {
842 0 : res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]);
843 0 : if (!res->qp[res->n])
844 0 : goto error;
845 0 : res->n++;
846 : }
847 :
848 0 : for (i = 0; i < fold2->n; ++i) {
849 0 : res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
850 0 : if (!res->qp[res->n])
851 0 : goto error;
852 0 : res->n++;
853 : }
854 :
855 0 : isl_qpolynomial_fold_free(fold1);
856 0 : isl_qpolynomial_fold_free(fold2);
857 :
858 0 : return res;
859 : error:
860 0 : isl_qpolynomial_fold_free(res);
861 0 : isl_qpolynomial_fold_free(fold1);
862 0 : isl_qpolynomial_fold_free(fold2);
863 0 : return NULL;
864 : }
865 :
866 0 : __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_fold(
867 : __isl_take isl_pw_qpolynomial_fold *pw1,
868 : __isl_take isl_pw_qpolynomial_fold *pw2)
869 : {
870 : int i, j, n;
871 : struct isl_pw_qpolynomial_fold *res;
872 : isl_set *set;
873 :
874 0 : if (!pw1 || !pw2)
875 : goto error;
876 :
877 0 : isl_assert(pw1->dim->ctx, isl_space_is_equal(pw1->dim, pw2->dim), goto error);
878 :
879 0 : if (isl_pw_qpolynomial_fold_is_zero(pw1)) {
880 0 : isl_pw_qpolynomial_fold_free(pw1);
881 0 : return pw2;
882 : }
883 :
884 0 : if (isl_pw_qpolynomial_fold_is_zero(pw2)) {
885 0 : isl_pw_qpolynomial_fold_free(pw2);
886 0 : return pw1;
887 : }
888 :
889 0 : if (pw1->type != pw2->type)
890 0 : isl_die(pw1->dim->ctx, isl_error_invalid,
891 : "fold types don't match", goto error);
892 :
893 0 : n = (pw1->n + 1) * (pw2->n + 1);
894 0 : res = isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pw1->dim),
895 : pw1->type, n);
896 :
897 0 : for (i = 0; i < pw1->n; ++i) {
898 0 : set = isl_set_copy(pw1->p[i].set);
899 0 : for (j = 0; j < pw2->n; ++j) {
900 : struct isl_set *common;
901 : isl_qpolynomial_fold *sum;
902 0 : set = isl_set_subtract(set,
903 0 : isl_set_copy(pw2->p[j].set));
904 0 : common = isl_set_intersect(isl_set_copy(pw1->p[i].set),
905 0 : isl_set_copy(pw2->p[j].set));
906 0 : if (isl_set_plain_is_empty(common)) {
907 0 : isl_set_free(common);
908 0 : continue;
909 : }
910 :
911 0 : sum = isl_qpolynomial_fold_fold_on_domain(common,
912 0 : isl_qpolynomial_fold_copy(pw1->p[i].fold),
913 0 : isl_qpolynomial_fold_copy(pw2->p[j].fold));
914 :
915 0 : res = isl_pw_qpolynomial_fold_add_piece(res, common, sum);
916 : }
917 0 : res = isl_pw_qpolynomial_fold_add_piece(res, set,
918 0 : isl_qpolynomial_fold_copy(pw1->p[i].fold));
919 : }
920 :
921 0 : for (j = 0; j < pw2->n; ++j) {
922 0 : set = isl_set_copy(pw2->p[j].set);
923 0 : for (i = 0; i < pw1->n; ++i)
924 0 : set = isl_set_subtract(set, isl_set_copy(pw1->p[i].set));
925 0 : res = isl_pw_qpolynomial_fold_add_piece(res, set,
926 0 : isl_qpolynomial_fold_copy(pw2->p[j].fold));
927 : }
928 :
929 0 : isl_pw_qpolynomial_fold_free(pw1);
930 0 : isl_pw_qpolynomial_fold_free(pw2);
931 :
932 0 : return res;
933 : error:
934 0 : isl_pw_qpolynomial_fold_free(pw1);
935 0 : isl_pw_qpolynomial_fold_free(pw2);
936 0 : return NULL;
937 : }
938 :
939 0 : __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
940 : __isl_take isl_union_pw_qpolynomial_fold *u,
941 : __isl_take isl_pw_qpolynomial_fold *part)
942 : {
943 : struct isl_hash_table_entry *entry;
944 :
945 0 : u = isl_union_pw_qpolynomial_fold_cow(u);
946 :
947 0 : if (!part || !u)
948 : goto error;
949 0 : if (isl_space_check_equal_params(part->dim, u->space) < 0)
950 0 : goto error;
951 :
952 0 : entry = isl_union_pw_qpolynomial_fold_find_part_entry(u, part->dim, 1);
953 0 : if (!entry)
954 0 : goto error;
955 :
956 0 : if (!entry->data)
957 0 : entry->data = part;
958 : else {
959 0 : entry->data = isl_pw_qpolynomial_fold_fold(entry->data,
960 : isl_pw_qpolynomial_fold_copy(part));
961 0 : if (!entry->data)
962 0 : goto error;
963 0 : isl_pw_qpolynomial_fold_free(part);
964 : }
965 :
966 0 : return u;
967 : error:
968 0 : isl_pw_qpolynomial_fold_free(part);
969 0 : isl_union_pw_qpolynomial_fold_free(u);
970 0 : return NULL;
971 : }
972 :
973 0 : static isl_stat fold_part(__isl_take isl_pw_qpolynomial_fold *part, void *user)
974 : {
975 : isl_union_pw_qpolynomial_fold **u;
976 0 : u = (isl_union_pw_qpolynomial_fold **)user;
977 :
978 0 : *u = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(*u, part);
979 :
980 0 : return isl_stat_ok;
981 : }
982 :
983 0 : __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold(
984 : __isl_take isl_union_pw_qpolynomial_fold *u1,
985 : __isl_take isl_union_pw_qpolynomial_fold *u2)
986 : {
987 0 : u1 = isl_union_pw_qpolynomial_fold_cow(u1);
988 :
989 0 : if (!u1 || !u2)
990 : goto error;
991 :
992 0 : if (isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(u2,
993 : &fold_part, &u1) < 0)
994 0 : goto error;
995 :
996 0 : isl_union_pw_qpolynomial_fold_free(u2);
997 :
998 0 : return u1;
999 : error:
1000 0 : isl_union_pw_qpolynomial_fold_free(u1);
1001 0 : isl_union_pw_qpolynomial_fold_free(u2);
1002 0 : return NULL;
1003 : }
1004 :
1005 0 : __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_from_pw_qpolynomial(
1006 : enum isl_fold type, __isl_take isl_pw_qpolynomial *pwqp)
1007 : {
1008 : int i;
1009 : isl_pw_qpolynomial_fold *pwf;
1010 :
1011 0 : if (!pwqp)
1012 0 : return NULL;
1013 :
1014 0 : pwf = isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pwqp->dim),
1015 : type, pwqp->n);
1016 :
1017 0 : for (i = 0; i < pwqp->n; ++i)
1018 0 : pwf = isl_pw_qpolynomial_fold_add_piece(pwf,
1019 0 : isl_set_copy(pwqp->p[i].set),
1020 : isl_qpolynomial_fold_alloc(type,
1021 0 : isl_qpolynomial_copy(pwqp->p[i].qp)));
1022 :
1023 0 : isl_pw_qpolynomial_free(pwqp);
1024 :
1025 0 : return pwf;
1026 : }
1027 :
1028 0 : __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_add(
1029 : __isl_take isl_pw_qpolynomial_fold *pwf1,
1030 : __isl_take isl_pw_qpolynomial_fold *pwf2)
1031 : {
1032 0 : return isl_pw_qpolynomial_fold_union_add_(pwf1, pwf2);
1033 : }
1034 :
1035 : /* Compare two quasi-polynomial reductions.
1036 : *
1037 : * Return -1 if "fold1" is "smaller" than "fold2", 1 if "fold1" is "greater"
1038 : * than "fold2" and 0 if they are equal.
1039 : */
1040 0 : int isl_qpolynomial_fold_plain_cmp(__isl_keep isl_qpolynomial_fold *fold1,
1041 : __isl_keep isl_qpolynomial_fold *fold2)
1042 : {
1043 : int i;
1044 :
1045 0 : if (fold1 == fold2)
1046 0 : return 0;
1047 0 : if (!fold1)
1048 0 : return -1;
1049 0 : if (!fold2)
1050 0 : return 1;
1051 :
1052 0 : if (fold1->n != fold2->n)
1053 0 : return fold1->n - fold2->n;
1054 :
1055 0 : for (i = 0; i < fold1->n; ++i) {
1056 : int cmp;
1057 :
1058 0 : cmp = isl_qpolynomial_plain_cmp(fold1->qp[i], fold2->qp[i]);
1059 0 : if (cmp != 0)
1060 0 : return cmp;
1061 : }
1062 :
1063 0 : return 0;
1064 : }
1065 :
1066 0 : int isl_qpolynomial_fold_plain_is_equal(__isl_keep isl_qpolynomial_fold *fold1,
1067 : __isl_keep isl_qpolynomial_fold *fold2)
1068 : {
1069 : int i;
1070 :
1071 0 : if (!fold1 || !fold2)
1072 0 : return -1;
1073 :
1074 0 : if (fold1->n != fold2->n)
1075 0 : return 0;
1076 :
1077 : /* We probably want to sort the qps first... */
1078 0 : for (i = 0; i < fold1->n; ++i) {
1079 0 : int eq = isl_qpolynomial_plain_is_equal(fold1->qp[i], fold2->qp[i]);
1080 0 : if (eq < 0 || !eq)
1081 0 : return eq;
1082 : }
1083 :
1084 0 : return 1;
1085 : }
1086 :
1087 0 : __isl_give isl_val *isl_qpolynomial_fold_eval(
1088 : __isl_take isl_qpolynomial_fold *fold, __isl_take isl_point *pnt)
1089 : {
1090 : isl_ctx *ctx;
1091 : isl_val *v;
1092 :
1093 0 : if (!fold || !pnt)
1094 : goto error;
1095 0 : ctx = isl_point_get_ctx(pnt);
1096 0 : isl_assert(pnt->dim->ctx, isl_space_is_equal(pnt->dim, fold->dim), goto error);
1097 0 : isl_assert(pnt->dim->ctx,
1098 : fold->type == isl_fold_max || fold->type == isl_fold_min,
1099 : goto error);
1100 :
1101 0 : if (fold->n == 0)
1102 0 : v = isl_val_zero(ctx);
1103 : else {
1104 : int i;
1105 0 : v = isl_qpolynomial_eval(isl_qpolynomial_copy(fold->qp[0]),
1106 : isl_point_copy(pnt));
1107 0 : for (i = 1; i < fold->n; ++i) {
1108 : isl_val *v_i;
1109 0 : v_i = isl_qpolynomial_eval(
1110 0 : isl_qpolynomial_copy(fold->qp[i]),
1111 : isl_point_copy(pnt));
1112 0 : if (fold->type == isl_fold_max)
1113 0 : v = isl_val_max(v, v_i);
1114 : else
1115 0 : v = isl_val_min(v, v_i);
1116 : }
1117 : }
1118 0 : isl_qpolynomial_fold_free(fold);
1119 0 : isl_point_free(pnt);
1120 :
1121 0 : return v;
1122 : error:
1123 0 : isl_qpolynomial_fold_free(fold);
1124 0 : isl_point_free(pnt);
1125 0 : return NULL;
1126 : }
1127 :
1128 0 : size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold *pwf)
1129 : {
1130 : int i;
1131 0 : size_t n = 0;
1132 :
1133 0 : for (i = 0; i < pwf->n; ++i)
1134 0 : n += pwf->p[i].fold->n;
1135 :
1136 0 : return n;
1137 : }
1138 :
1139 0 : __isl_give isl_val *isl_qpolynomial_fold_opt_on_domain(
1140 : __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *set, int max)
1141 : {
1142 : int i;
1143 : isl_val *opt;
1144 :
1145 0 : if (!set || !fold)
1146 : goto error;
1147 :
1148 0 : if (fold->n == 0) {
1149 0 : opt = isl_val_zero(isl_set_get_ctx(set));
1150 0 : isl_set_free(set);
1151 0 : isl_qpolynomial_fold_free(fold);
1152 0 : return opt;
1153 : }
1154 :
1155 0 : opt = isl_qpolynomial_opt_on_domain(isl_qpolynomial_copy(fold->qp[0]),
1156 : isl_set_copy(set), max);
1157 0 : for (i = 1; i < fold->n; ++i) {
1158 : isl_val *opt_i;
1159 0 : opt_i = isl_qpolynomial_opt_on_domain(
1160 0 : isl_qpolynomial_copy(fold->qp[i]),
1161 : isl_set_copy(set), max);
1162 0 : if (max)
1163 0 : opt = isl_val_max(opt, opt_i);
1164 : else
1165 0 : opt = isl_val_min(opt, opt_i);
1166 : }
1167 :
1168 0 : isl_set_free(set);
1169 0 : isl_qpolynomial_fold_free(fold);
1170 :
1171 0 : return opt;
1172 : error:
1173 0 : isl_set_free(set);
1174 0 : isl_qpolynomial_fold_free(fold);
1175 0 : return NULL;
1176 : }
1177 :
1178 : /* Check whether for each quasi-polynomial in "fold2" there is
1179 : * a quasi-polynomial in "fold1" that dominates it on "set".
1180 : */
1181 0 : static int qpolynomial_fold_covers_on_domain(__isl_keep isl_set *set,
1182 : __isl_keep isl_qpolynomial_fold *fold1,
1183 : __isl_keep isl_qpolynomial_fold *fold2)
1184 : {
1185 : int i, j;
1186 : int covers;
1187 :
1188 0 : if (!set || !fold1 || !fold2)
1189 0 : return -1;
1190 :
1191 0 : covers = fold1->type == isl_fold_max ? 1 : -1;
1192 :
1193 0 : for (i = 0; i < fold2->n; ++i) {
1194 0 : for (j = 0; j < fold1->n; ++j) {
1195 : isl_qpolynomial *d;
1196 : int sgn;
1197 :
1198 0 : d = isl_qpolynomial_sub(
1199 0 : isl_qpolynomial_copy(fold1->qp[j]),
1200 0 : isl_qpolynomial_copy(fold2->qp[i]));
1201 0 : sgn = isl_qpolynomial_sign(set, d);
1202 0 : isl_qpolynomial_free(d);
1203 0 : if (sgn == covers)
1204 0 : break;
1205 : }
1206 0 : if (j >= fold1->n)
1207 0 : return 0;
1208 : }
1209 :
1210 0 : return 1;
1211 : }
1212 :
1213 : /* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains
1214 : * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates
1215 : * that of pwf2.
1216 : */
1217 0 : int isl_pw_qpolynomial_fold_covers(__isl_keep isl_pw_qpolynomial_fold *pwf1,
1218 : __isl_keep isl_pw_qpolynomial_fold *pwf2)
1219 : {
1220 : int i, j;
1221 : isl_set *dom1, *dom2;
1222 : int is_subset;
1223 :
1224 0 : if (!pwf1 || !pwf2)
1225 0 : return -1;
1226 :
1227 0 : if (pwf2->n == 0)
1228 0 : return 1;
1229 0 : if (pwf1->n == 0)
1230 0 : return 0;
1231 :
1232 0 : dom1 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1));
1233 0 : dom2 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2));
1234 0 : is_subset = isl_set_is_subset(dom2, dom1);
1235 0 : isl_set_free(dom1);
1236 0 : isl_set_free(dom2);
1237 :
1238 0 : if (is_subset < 0 || !is_subset)
1239 0 : return is_subset;
1240 :
1241 0 : for (i = 0; i < pwf2->n; ++i) {
1242 0 : for (j = 0; j < pwf1->n; ++j) {
1243 : int is_empty;
1244 : isl_set *common;
1245 : int covers;
1246 :
1247 0 : common = isl_set_intersect(isl_set_copy(pwf1->p[j].set),
1248 0 : isl_set_copy(pwf2->p[i].set));
1249 0 : is_empty = isl_set_is_empty(common);
1250 0 : if (is_empty < 0 || is_empty) {
1251 0 : isl_set_free(common);
1252 0 : if (is_empty < 0)
1253 0 : return -1;
1254 0 : continue;
1255 : }
1256 0 : covers = qpolynomial_fold_covers_on_domain(common,
1257 0 : pwf1->p[j].fold, pwf2->p[i].fold);
1258 0 : isl_set_free(common);
1259 0 : if (covers < 0 || !covers)
1260 0 : return covers;
1261 : }
1262 : }
1263 :
1264 0 : return 1;
1265 : }
1266 :
1267 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_morph_domain(
1268 : __isl_take isl_qpolynomial_fold *fold, __isl_take isl_morph *morph)
1269 : {
1270 : int i;
1271 : isl_ctx *ctx;
1272 :
1273 0 : if (!fold || !morph)
1274 : goto error;
1275 :
1276 0 : ctx = fold->dim->ctx;
1277 0 : isl_assert(ctx, isl_space_is_equal(fold->dim, morph->dom->dim), goto error);
1278 :
1279 0 : fold = isl_qpolynomial_fold_cow(fold);
1280 0 : if (!fold)
1281 0 : goto error;
1282 :
1283 0 : isl_space_free(fold->dim);
1284 0 : fold->dim = isl_space_copy(morph->ran->dim);
1285 0 : if (!fold->dim)
1286 0 : goto error;
1287 :
1288 0 : for (i = 0; i < fold->n; ++i) {
1289 0 : fold->qp[i] = isl_qpolynomial_morph_domain(fold->qp[i],
1290 : isl_morph_copy(morph));
1291 0 : if (!fold->qp[i])
1292 0 : goto error;
1293 : }
1294 :
1295 0 : isl_morph_free(morph);
1296 :
1297 0 : return fold;
1298 : error:
1299 0 : isl_qpolynomial_fold_free(fold);
1300 0 : isl_morph_free(morph);
1301 0 : return NULL;
1302 : }
1303 :
1304 0 : enum isl_fold isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold *fold)
1305 : {
1306 0 : if (!fold)
1307 0 : return isl_fold_list;
1308 0 : return fold->type;
1309 : }
1310 :
1311 0 : enum isl_fold isl_union_pw_qpolynomial_fold_get_type(
1312 : __isl_keep isl_union_pw_qpolynomial_fold *upwf)
1313 : {
1314 0 : if (!upwf)
1315 0 : return isl_fold_list;
1316 0 : return upwf->type;
1317 : }
1318 :
1319 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_lift(
1320 : __isl_take isl_qpolynomial_fold *fold, __isl_take isl_space *dim)
1321 : {
1322 : int i;
1323 :
1324 0 : if (!fold || !dim)
1325 : goto error;
1326 :
1327 0 : if (isl_space_is_equal(fold->dim, dim)) {
1328 0 : isl_space_free(dim);
1329 0 : return fold;
1330 : }
1331 :
1332 0 : fold = isl_qpolynomial_fold_cow(fold);
1333 0 : if (!fold)
1334 0 : goto error;
1335 :
1336 0 : isl_space_free(fold->dim);
1337 0 : fold->dim = isl_space_copy(dim);
1338 0 : if (!fold->dim)
1339 0 : goto error;
1340 :
1341 0 : for (i = 0; i < fold->n; ++i) {
1342 0 : fold->qp[i] = isl_qpolynomial_lift(fold->qp[i],
1343 : isl_space_copy(dim));
1344 0 : if (!fold->qp[i])
1345 0 : goto error;
1346 : }
1347 :
1348 0 : isl_space_free(dim);
1349 :
1350 0 : return fold;
1351 : error:
1352 0 : isl_qpolynomial_fold_free(fold);
1353 0 : isl_space_free(dim);
1354 0 : return NULL;
1355 : }
1356 :
1357 0 : isl_stat isl_qpolynomial_fold_foreach_qpolynomial(
1358 : __isl_keep isl_qpolynomial_fold *fold,
1359 : isl_stat (*fn)(__isl_take isl_qpolynomial *qp, void *user), void *user)
1360 : {
1361 : int i;
1362 :
1363 0 : if (!fold)
1364 0 : return isl_stat_error;
1365 :
1366 0 : for (i = 0; i < fold->n; ++i)
1367 0 : if (fn(isl_qpolynomial_copy(fold->qp[i]), user) < 0)
1368 0 : return isl_stat_error;
1369 :
1370 0 : return isl_stat_ok;
1371 : }
1372 :
1373 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_move_dims(
1374 : __isl_take isl_qpolynomial_fold *fold,
1375 : enum isl_dim_type dst_type, unsigned dst_pos,
1376 : enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1377 : {
1378 : int i;
1379 : enum isl_dim_type set_src_type, set_dst_type;
1380 :
1381 0 : if (n == 0)
1382 0 : return fold;
1383 :
1384 0 : fold = isl_qpolynomial_fold_cow(fold);
1385 0 : if (!fold)
1386 0 : return NULL;
1387 :
1388 0 : set_src_type = domain_type(src_type);
1389 0 : set_dst_type = domain_type(dst_type);
1390 :
1391 0 : fold->dim = isl_space_move_dims(fold->dim, set_dst_type, dst_pos,
1392 : set_src_type, src_pos, n);
1393 0 : if (!fold->dim)
1394 0 : goto error;
1395 :
1396 0 : for (i = 0; i < fold->n; ++i) {
1397 0 : fold->qp[i] = isl_qpolynomial_move_dims(fold->qp[i],
1398 : dst_type, dst_pos, src_type, src_pos, n);
1399 0 : if (!fold->qp[i])
1400 0 : goto error;
1401 : }
1402 :
1403 0 : return fold;
1404 : error:
1405 0 : isl_qpolynomial_fold_free(fold);
1406 0 : return NULL;
1407 : }
1408 :
1409 : /* For each 0 <= i < "n", replace variable "first" + i of type "type"
1410 : * in fold->qp[k] by subs[i].
1411 : */
1412 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute(
1413 : __isl_take isl_qpolynomial_fold *fold,
1414 : enum isl_dim_type type, unsigned first, unsigned n,
1415 : __isl_keep isl_qpolynomial **subs)
1416 : {
1417 : int i;
1418 :
1419 0 : if (n == 0)
1420 0 : return fold;
1421 :
1422 0 : fold = isl_qpolynomial_fold_cow(fold);
1423 0 : if (!fold)
1424 0 : return NULL;
1425 :
1426 0 : for (i = 0; i < fold->n; ++i) {
1427 0 : fold->qp[i] = isl_qpolynomial_substitute(fold->qp[i],
1428 : type, first, n, subs);
1429 0 : if (!fold->qp[i])
1430 0 : goto error;
1431 : }
1432 :
1433 0 : return fold;
1434 : error:
1435 0 : isl_qpolynomial_fold_free(fold);
1436 0 : return NULL;
1437 : }
1438 :
1439 0 : static isl_stat add_pwqp(__isl_take isl_pw_qpolynomial *pwqp, void *user)
1440 : {
1441 : isl_pw_qpolynomial_fold *pwf;
1442 : isl_union_pw_qpolynomial_fold **upwf;
1443 : struct isl_hash_table_entry *entry;
1444 :
1445 0 : upwf = (isl_union_pw_qpolynomial_fold **)user;
1446 :
1447 0 : entry = isl_union_pw_qpolynomial_fold_find_part_entry(*upwf,
1448 : pwqp->dim, 1);
1449 0 : if (!entry)
1450 0 : goto error;
1451 :
1452 0 : pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial((*upwf)->type, pwqp);
1453 0 : if (!entry->data)
1454 0 : entry->data = pwf;
1455 : else {
1456 0 : entry->data = isl_pw_qpolynomial_fold_add(entry->data, pwf);
1457 0 : if (!entry->data)
1458 0 : return isl_stat_error;
1459 0 : if (isl_pw_qpolynomial_fold_is_zero(entry->data))
1460 0 : *upwf = isl_union_pw_qpolynomial_fold_remove_part_entry(
1461 : *upwf, entry);
1462 : }
1463 :
1464 0 : return isl_stat_ok;
1465 : error:
1466 0 : isl_pw_qpolynomial_free(pwqp);
1467 0 : return isl_stat_error;
1468 : }
1469 :
1470 0 : __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial(
1471 : __isl_take isl_union_pw_qpolynomial_fold *upwf,
1472 : __isl_take isl_union_pw_qpolynomial *upwqp)
1473 : {
1474 0 : upwf = isl_union_pw_qpolynomial_fold_align_params(upwf,
1475 : isl_union_pw_qpolynomial_get_space(upwqp));
1476 0 : upwqp = isl_union_pw_qpolynomial_align_params(upwqp,
1477 : isl_union_pw_qpolynomial_fold_get_space(upwf));
1478 :
1479 0 : upwf = isl_union_pw_qpolynomial_fold_cow(upwf);
1480 0 : if (!upwf || !upwqp)
1481 : goto error;
1482 :
1483 0 : if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp, &add_pwqp,
1484 : &upwf) < 0)
1485 0 : goto error;
1486 :
1487 0 : isl_union_pw_qpolynomial_free(upwqp);
1488 :
1489 0 : return upwf;
1490 : error:
1491 0 : isl_union_pw_qpolynomial_fold_free(upwf);
1492 0 : isl_union_pw_qpolynomial_free(upwqp);
1493 0 : return NULL;
1494 : }
1495 :
1496 0 : static isl_bool join_compatible(__isl_keep isl_space *space1,
1497 : __isl_keep isl_space *space2)
1498 : {
1499 : isl_bool m;
1500 0 : m = isl_space_has_equal_params(space1, space2);
1501 0 : if (m < 0 || !m)
1502 0 : return m;
1503 0 : return isl_space_tuple_is_equal(space1, isl_dim_out,
1504 : space2, isl_dim_in);
1505 : }
1506 :
1507 : /* Compute the intersection of the range of the map and the domain
1508 : * of the piecewise quasipolynomial reduction and then compute a bound
1509 : * on the associated quasipolynomial reduction over all elements
1510 : * in this intersection.
1511 : *
1512 : * We first introduce some unconstrained dimensions in the
1513 : * piecewise quasipolynomial, intersect the resulting domain
1514 : * with the wrapped map and the compute the sum.
1515 : */
1516 0 : __isl_give isl_pw_qpolynomial_fold *isl_map_apply_pw_qpolynomial_fold(
1517 : __isl_take isl_map *map, __isl_take isl_pw_qpolynomial_fold *pwf,
1518 : int *tight)
1519 : {
1520 : isl_ctx *ctx;
1521 : isl_set *dom;
1522 : isl_space *map_dim;
1523 : isl_space *pwf_dim;
1524 : unsigned n_in;
1525 : isl_bool ok;
1526 :
1527 0 : ctx = isl_map_get_ctx(map);
1528 0 : if (!ctx)
1529 0 : goto error;
1530 :
1531 0 : map_dim = isl_map_get_space(map);
1532 0 : pwf_dim = isl_pw_qpolynomial_fold_get_space(pwf);
1533 0 : ok = join_compatible(map_dim, pwf_dim);
1534 0 : isl_space_free(map_dim);
1535 0 : isl_space_free(pwf_dim);
1536 0 : if (ok < 0)
1537 0 : goto error;
1538 0 : if (!ok)
1539 0 : isl_die(ctx, isl_error_invalid, "incompatible dimensions",
1540 : goto error);
1541 :
1542 0 : n_in = isl_map_dim(map, isl_dim_in);
1543 0 : pwf = isl_pw_qpolynomial_fold_insert_dims(pwf, isl_dim_in, 0, n_in);
1544 :
1545 0 : dom = isl_map_wrap(map);
1546 0 : pwf = isl_pw_qpolynomial_fold_reset_domain_space(pwf,
1547 : isl_set_get_space(dom));
1548 :
1549 0 : pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, dom);
1550 0 : pwf = isl_pw_qpolynomial_fold_bound(pwf, tight);
1551 :
1552 0 : return pwf;
1553 : error:
1554 0 : isl_map_free(map);
1555 0 : isl_pw_qpolynomial_fold_free(pwf);
1556 0 : return NULL;
1557 : }
1558 :
1559 0 : __isl_give isl_pw_qpolynomial_fold *isl_set_apply_pw_qpolynomial_fold(
1560 : __isl_take isl_set *set, __isl_take isl_pw_qpolynomial_fold *pwf,
1561 : int *tight)
1562 : {
1563 0 : return isl_map_apply_pw_qpolynomial_fold(set, pwf, tight);
1564 : }
1565 :
1566 : struct isl_apply_fold_data {
1567 : isl_union_pw_qpolynomial_fold *upwf;
1568 : isl_union_pw_qpolynomial_fold *res;
1569 : isl_map *map;
1570 : int tight;
1571 : };
1572 :
1573 0 : static isl_stat pw_qpolynomial_fold_apply(
1574 : __isl_take isl_pw_qpolynomial_fold *pwf, void *user)
1575 : {
1576 : isl_space *map_dim;
1577 : isl_space *pwf_dim;
1578 0 : struct isl_apply_fold_data *data = user;
1579 : isl_bool ok;
1580 :
1581 0 : map_dim = isl_map_get_space(data->map);
1582 0 : pwf_dim = isl_pw_qpolynomial_fold_get_space(pwf);
1583 0 : ok = join_compatible(map_dim, pwf_dim);
1584 0 : isl_space_free(map_dim);
1585 0 : isl_space_free(pwf_dim);
1586 :
1587 0 : if (ok < 0)
1588 0 : return isl_stat_error;
1589 0 : if (ok) {
1590 0 : pwf = isl_map_apply_pw_qpolynomial_fold(isl_map_copy(data->map),
1591 0 : pwf, data->tight ? &data->tight : NULL);
1592 0 : data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
1593 : data->res, pwf);
1594 : } else
1595 0 : isl_pw_qpolynomial_fold_free(pwf);
1596 :
1597 0 : return isl_stat_ok;
1598 : }
1599 :
1600 0 : static isl_stat map_apply(__isl_take isl_map *map, void *user)
1601 : {
1602 0 : struct isl_apply_fold_data *data = user;
1603 : isl_stat r;
1604 :
1605 0 : data->map = map;
1606 0 : r = isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(
1607 : data->upwf, &pw_qpolynomial_fold_apply, data);
1608 :
1609 0 : isl_map_free(map);
1610 0 : return r;
1611 : }
1612 :
1613 0 : __isl_give isl_union_pw_qpolynomial_fold *isl_union_map_apply_union_pw_qpolynomial_fold(
1614 : __isl_take isl_union_map *umap,
1615 : __isl_take isl_union_pw_qpolynomial_fold *upwf, int *tight)
1616 : {
1617 : isl_space *dim;
1618 : enum isl_fold type;
1619 : struct isl_apply_fold_data data;
1620 :
1621 0 : upwf = isl_union_pw_qpolynomial_fold_align_params(upwf,
1622 : isl_union_map_get_space(umap));
1623 0 : umap = isl_union_map_align_params(umap,
1624 : isl_union_pw_qpolynomial_fold_get_space(upwf));
1625 :
1626 0 : data.upwf = upwf;
1627 0 : data.tight = tight ? 1 : 0;
1628 0 : dim = isl_union_pw_qpolynomial_fold_get_space(upwf);
1629 0 : type = isl_union_pw_qpolynomial_fold_get_type(upwf);
1630 0 : data.res = isl_union_pw_qpolynomial_fold_zero(dim, type);
1631 0 : if (isl_union_map_foreach_map(umap, &map_apply, &data) < 0)
1632 0 : goto error;
1633 :
1634 0 : isl_union_map_free(umap);
1635 0 : isl_union_pw_qpolynomial_fold_free(upwf);
1636 :
1637 0 : if (tight)
1638 0 : *tight = data.tight;
1639 :
1640 0 : return data.res;
1641 : error:
1642 0 : isl_union_map_free(umap);
1643 0 : isl_union_pw_qpolynomial_fold_free(upwf);
1644 0 : isl_union_pw_qpolynomial_fold_free(data.res);
1645 0 : return NULL;
1646 : }
1647 :
1648 0 : __isl_give isl_union_pw_qpolynomial_fold *isl_union_set_apply_union_pw_qpolynomial_fold(
1649 : __isl_take isl_union_set *uset,
1650 : __isl_take isl_union_pw_qpolynomial_fold *upwf, int *tight)
1651 : {
1652 0 : return isl_union_map_apply_union_pw_qpolynomial_fold(uset, upwf, tight);
1653 : }
1654 :
1655 : /* Reorder the dimension of "fold" according to the given reordering.
1656 : */
1657 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_realign_domain(
1658 : __isl_take isl_qpolynomial_fold *fold, __isl_take isl_reordering *r)
1659 : {
1660 : int i;
1661 : isl_space *space;
1662 :
1663 0 : fold = isl_qpolynomial_fold_cow(fold);
1664 0 : if (!fold || !r)
1665 : goto error;
1666 :
1667 0 : for (i = 0; i < fold->n; ++i) {
1668 0 : fold->qp[i] = isl_qpolynomial_realign_domain(fold->qp[i],
1669 : isl_reordering_copy(r));
1670 0 : if (!fold->qp[i])
1671 0 : goto error;
1672 : }
1673 :
1674 0 : space = isl_reordering_get_space(r);
1675 0 : fold = isl_qpolynomial_fold_reset_domain_space(fold, space);
1676 :
1677 0 : isl_reordering_free(r);
1678 :
1679 0 : return fold;
1680 : error:
1681 0 : isl_qpolynomial_fold_free(fold);
1682 0 : isl_reordering_free(r);
1683 0 : return NULL;
1684 : }
1685 :
1686 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_mul_isl_int(
1687 : __isl_take isl_qpolynomial_fold *fold, isl_int v)
1688 : {
1689 : int i;
1690 :
1691 0 : if (isl_int_is_one(v))
1692 0 : return fold;
1693 0 : if (fold && isl_int_is_zero(v)) {
1694 : isl_qpolynomial_fold *zero;
1695 0 : isl_space *dim = isl_space_copy(fold->dim);
1696 0 : zero = isl_qpolynomial_fold_empty(fold->type, dim);
1697 0 : isl_qpolynomial_fold_free(fold);
1698 0 : return zero;
1699 : }
1700 :
1701 0 : fold = isl_qpolynomial_fold_cow(fold);
1702 0 : if (!fold)
1703 0 : return NULL;
1704 :
1705 0 : if (isl_int_is_neg(v))
1706 0 : fold->type = isl_fold_type_negate(fold->type);
1707 0 : for (i = 0; i < fold->n; ++i) {
1708 0 : fold->qp[i] = isl_qpolynomial_mul_isl_int(fold->qp[i], v);
1709 0 : if (!fold->qp[i])
1710 0 : goto error;
1711 : }
1712 :
1713 0 : return fold;
1714 : error:
1715 0 : isl_qpolynomial_fold_free(fold);
1716 0 : return NULL;
1717 : }
1718 :
1719 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale(
1720 : __isl_take isl_qpolynomial_fold *fold, isl_int v)
1721 : {
1722 0 : return isl_qpolynomial_fold_mul_isl_int(fold, v);
1723 : }
1724 :
1725 : /* Multiply "fold" by "v".
1726 : */
1727 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale_val(
1728 : __isl_take isl_qpolynomial_fold *fold, __isl_take isl_val *v)
1729 : {
1730 : int i;
1731 :
1732 0 : if (!fold || !v)
1733 : goto error;
1734 :
1735 0 : if (isl_val_is_one(v)) {
1736 0 : isl_val_free(v);
1737 0 : return fold;
1738 : }
1739 0 : if (isl_val_is_zero(v)) {
1740 : isl_qpolynomial_fold *zero;
1741 0 : isl_space *space = isl_qpolynomial_fold_get_domain_space(fold);
1742 0 : zero = isl_qpolynomial_fold_empty(fold->type, space);
1743 0 : isl_qpolynomial_fold_free(fold);
1744 0 : isl_val_free(v);
1745 0 : return zero;
1746 : }
1747 0 : if (!isl_val_is_rat(v))
1748 0 : isl_die(isl_qpolynomial_fold_get_ctx(fold), isl_error_invalid,
1749 : "expecting rational factor", goto error);
1750 :
1751 0 : fold = isl_qpolynomial_fold_cow(fold);
1752 0 : if (!fold)
1753 0 : goto error;
1754 :
1755 0 : if (isl_val_is_neg(v))
1756 0 : fold->type = isl_fold_type_negate(fold->type);
1757 0 : for (i = 0; i < fold->n; ++i) {
1758 0 : fold->qp[i] = isl_qpolynomial_scale_val(fold->qp[i],
1759 : isl_val_copy(v));
1760 0 : if (!fold->qp[i])
1761 0 : goto error;
1762 : }
1763 :
1764 0 : isl_val_free(v);
1765 0 : return fold;
1766 : error:
1767 0 : isl_val_free(v);
1768 0 : isl_qpolynomial_fold_free(fold);
1769 0 : return NULL;
1770 : }
1771 :
1772 : /* Divide "fold" by "v".
1773 : */
1774 0 : __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale_down_val(
1775 : __isl_take isl_qpolynomial_fold *fold, __isl_take isl_val *v)
1776 : {
1777 0 : if (!fold || !v)
1778 : goto error;
1779 :
1780 0 : if (isl_val_is_one(v)) {
1781 0 : isl_val_free(v);
1782 0 : return fold;
1783 : }
1784 0 : if (!isl_val_is_rat(v))
1785 0 : isl_die(isl_qpolynomial_fold_get_ctx(fold), isl_error_invalid,
1786 : "expecting rational factor", goto error);
1787 0 : if (isl_val_is_zero(v))
1788 0 : isl_die(isl_val_get_ctx(v), isl_error_invalid,
1789 : "cannot scale down by zero", goto error);
1790 :
1791 0 : return isl_qpolynomial_fold_scale_val(fold, isl_val_inv(v));
1792 : error:
1793 0 : isl_val_free(v);
1794 0 : isl_qpolynomial_fold_free(fold);
1795 0 : return NULL;
1796 : }
|
