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