?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_map_simplify.c: isl_basic_map_eliminate_vars: drop redundant mark removal
[isl.git] / isl_fold.c
blob9e1196ac5e5f3ad52ee01d73817ac5898bed0cb2
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 *dim, int n)
44 {
45 isl_qpolynomial_fold *fold;
46
47 if (!dim)
48 goto error;
49
50 isl_assert(dim->ctx, n >= 0, goto error);
51 fold = isl_calloc(dim->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 = dim;
62
63 return fold;
64 error:
65 isl_space_free(dim);
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 struct isl_upoly_cst *cst;
263
264 if (isl_qpolynomial_is_nan(qp))
265 return 0;
266
267 cst = isl_upoly_as_cst(qp->upoly);
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 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 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_upoly_as_rec(qp->upoly);
357 if (!rec)
358 return 0;
359
360 d = isl_space_dim(qp->dim, isl_dim_all);
361 v = isl_vec_alloc(set->ctx, 2 + d);
362 if (!v)
363 return 0;
364
365 isl_seq_clr(v->el + 1, 1 + d);
366 isl_int_set_si(v->el[0], 1);
367 isl_int_set_si(v->el[2 + qp->upoly->var], 1);
368
369 isl_int_init(l);
370
371 res = isl_set_solve_lp(set, 0, v->el + 1, v->el[0], &l, NULL, NULL);
372 if (res == isl_lp_ok) {
373 isl_qpolynomial *min;
374 isl_qpolynomial *base;
375 isl_qpolynomial *r, *q;
376 isl_qpolynomial *t;
377
378 min = isl_qpolynomial_cst_on_domain(isl_space_copy(qp->dim), l);
379 base = isl_qpolynomial_var_pow_on_domain(isl_space_copy(qp->dim),
380 qp->upoly->var, 1);
381
382 r = isl_qpolynomial_alloc(isl_space_copy(qp->dim), 0,
383 isl_upoly_copy(rec->p[rec->n - 1]));
384 q = isl_qpolynomial_copy(r);
385
386 for (i = rec->n - 2; i >= 0; --i) {
387 r = isl_qpolynomial_mul(r, isl_qpolynomial_copy(min));
388 t = isl_qpolynomial_alloc(isl_space_copy(qp->dim), 0,
389 isl_upoly_copy(rec->p[i]));
390 r = isl_qpolynomial_add(r, t);
391 if (i == 0)
392 break;
393 q = isl_qpolynomial_mul(q, isl_qpolynomial_copy(base));
394 q = isl_qpolynomial_add(q, isl_qpolynomial_copy(r));
395 }
396
397 if (isl_qpolynomial_is_zero(q))
398 sgn = isl_qpolynomial_sign(set, r);
399 else if (isl_qpolynomial_is_zero(r))
400 sgn = isl_qpolynomial_sign(set, q);
401 else {
402 int sgn_q, sgn_r;
403 sgn_r = isl_qpolynomial_sign(set, r);
404 sgn_q = isl_qpolynomial_sign(set, q);
405 if (sgn_r == sgn_q)
406 sgn = sgn_r;
407 }
408
409 isl_qpolynomial_free(min);
410 isl_qpolynomial_free(base);
411 isl_qpolynomial_free(q);
412 isl_qpolynomial_free(r);
413 }
414
415 isl_int_clear(l);
416
417 isl_vec_free(v);
418
419 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 __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 struct isl_qpolynomial_fold *res = NULL;
438 int better;
439
440 if (!fold1 || !fold2)
441 goto error;
442
443 isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error);
444 isl_assert(fold1->dim->ctx, isl_space_is_equal(fold1->dim, fold2->dim),
445 goto error);
446
447 better = fold1->type == isl_fold_max ? -1 : 1;
448
449 if (isl_qpolynomial_fold_is_empty(fold1) ||
450 isl_qpolynomial_fold_is_nan(fold2)) {
451 isl_qpolynomial_fold_free(fold1);
452 return fold2;
453 }
454
455 if (isl_qpolynomial_fold_is_empty(fold2) ||
456 isl_qpolynomial_fold_is_nan(fold1)) {
457 isl_qpolynomial_fold_free(fold2);
458 return fold1;
459 }
460
461 res = qpolynomial_fold_alloc(fold1->type, isl_space_copy(fold1->dim),
462 fold1->n + fold2->n);
463 if (!res)
464 goto error;
465
466 for (i = 0; i < fold1->n; ++i) {
467 res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]);
468 if (!res->qp[res->n])
469 goto error;
470 res->n++;
471 }
472 n1 = res->n;
473
474 for (i = 0; i < fold2->n; ++i) {
475 for (j = n1 - 1; j >= 0; --j) {
476 isl_qpolynomial *d;
477 int sgn, equal;
478 equal = isl_qpolynomial_plain_is_equal(res->qp[j],
479 fold2->qp[i]);
480 if (equal < 0)
481 goto error;
482 if (equal)
483 break;
484 d = isl_qpolynomial_sub(
485 isl_qpolynomial_copy(res->qp[j]),
486 isl_qpolynomial_copy(fold2->qp[i]));
487 sgn = isl_qpolynomial_sign(set, d);
488 isl_qpolynomial_free(d);
489 if (sgn == 0)
490 continue;
491 if (sgn != better)
492 break;
493 isl_qpolynomial_free(res->qp[j]);
494 if (j != n1 - 1)
495 res->qp[j] = res->qp[n1 - 1];
496 n1--;
497 if (n1 != res->n - 1)
498 res->qp[n1] = res->qp[res->n - 1];
499 res->n--;
500 }
501 if (j >= 0)
502 continue;
503 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
504 if (!res->qp[res->n])
505 goto error;
506 res->n++;
507 }
508
509 isl_qpolynomial_fold_free(fold1);
510 isl_qpolynomial_fold_free(fold2);
511
512 return res;
513 error:
514 isl_qpolynomial_fold_free(res);
515 isl_qpolynomial_fold_free(fold1);
516 isl_qpolynomial_fold_free(fold2);
517 return NULL;
518 }
519
520 __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 if (!fold || !qp)
526 goto error;
527
528 if (isl_qpolynomial_is_zero(qp)) {
529 isl_qpolynomial_free(qp);
530 return fold;
531 }
532
533 fold = isl_qpolynomial_fold_cow(fold);
534 if (!fold)
535 goto error;
536
537 for (i = 0; i < fold->n; ++i) {
538 fold->qp[i] = isl_qpolynomial_add(fold->qp[i],
539 isl_qpolynomial_copy(qp));
540 if (!fold->qp[i])
541 goto error;
542 }
543
544 isl_qpolynomial_free(qp);
545 return fold;
546 error:
547 isl_qpolynomial_fold_free(fold);
548 isl_qpolynomial_free(qp);
549 return NULL;
550 }
551
552 __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 isl_qpolynomial_fold *res = NULL;
559
560 if (!fold1 || !fold2)
561 goto error;
562
563 if (isl_qpolynomial_fold_is_empty(fold1)) {
564 isl_qpolynomial_fold_free(fold1);
565 return fold2;
566 }
567
568 if (isl_qpolynomial_fold_is_empty(fold2)) {
569 isl_qpolynomial_fold_free(fold2);
570 return fold1;
571 }
572
573 if (fold1->n == 1 && fold2->n != 1)
574 return isl_qpolynomial_fold_add_on_domain(dom, fold2, fold1);
575
576 if (fold2->n == 1) {
577 res = isl_qpolynomial_fold_add_qpolynomial(fold1,
578 isl_qpolynomial_copy(fold2->qp[0]));
579 isl_qpolynomial_fold_free(fold2);
580 return res;
581 }
582
583 res = isl_qpolynomial_fold_add_qpolynomial(
584 isl_qpolynomial_fold_copy(fold1),
585 isl_qpolynomial_copy(fold2->qp[0]));
586
587 for (i = 1; i < fold2->n; ++i) {
588 isl_qpolynomial_fold *res_i;
589 res_i = isl_qpolynomial_fold_add_qpolynomial(
590 isl_qpolynomial_fold_copy(fold1),
591 isl_qpolynomial_copy(fold2->qp[i]));
592 res = isl_qpolynomial_fold_fold_on_domain(dom, res, res_i);
593 }
594
595 isl_qpolynomial_fold_free(fold1);
596 isl_qpolynomial_fold_free(fold2);
597 return res;
598 error:
599 isl_qpolynomial_fold_free(res);
600 isl_qpolynomial_fold_free(fold1);
601 isl_qpolynomial_fold_free(fold2);
602 return NULL;
603 }
604
605 __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 if (!fold || !eq)
611 goto error;
612
613 fold = isl_qpolynomial_fold_cow(fold);
614 if (!fold)
615 return NULL;
616
617 for (i = 0; i < fold->n; ++i) {
618 fold->qp[i] = isl_qpolynomial_substitute_equalities(fold->qp[i],
619 isl_basic_set_copy(eq));
620 if (!fold->qp[i])
621 goto error;
622 }
623
624 isl_basic_set_free(eq);
625 return fold;
626 error:
627 isl_basic_set_free(eq);
628 isl_qpolynomial_fold_free(fold);
629 return NULL;
630 }
631
632 __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 if (!fold || !context)
638 goto error;
639
640 fold = isl_qpolynomial_fold_cow(fold);
641 if (!fold)
642 return NULL;
643
644 for (i = 0; i < fold->n; ++i) {
645 fold->qp[i] = isl_qpolynomial_gist(fold->qp[i],
646 isl_set_copy(context));
647 if (!fold->qp[i])
648 goto error;
649 }
650
651 isl_set_free(context);
652 return fold;
653 error:
654 isl_set_free(context);
655 isl_qpolynomial_fold_free(fold);
656 return NULL;
657 }
658
659 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_gist_params(
660 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *context)
661 {
662 isl_space *space = isl_qpolynomial_fold_get_domain_space(fold);
663 isl_set *dom_context = isl_set_universe(space);
664 dom_context = isl_set_intersect_params(dom_context, context);
665 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 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_empty(enum isl_fold type,
703 __isl_take isl_space *dim)
704 {
705 return qpolynomial_fold_alloc(type, dim, 0);
706 }
707
708 __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 if (!qp)
714 return NULL;
715
716 fold = qpolynomial_fold_alloc(type, isl_space_copy(qp->dim), 1);
717 if (!fold)
718 goto error;
719
720 fold->qp[0] = qp;
721 fold->n++;
722
723 return fold;
724 error:
725 isl_qpolynomial_fold_free(fold);
726 isl_qpolynomial_free(qp);
727 return NULL;
728 }
729
730 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_copy(
731 __isl_keep isl_qpolynomial_fold *fold)
732 {
733 if (!fold)
734 return NULL;
735
736 fold->ref++;
737 return fold;
738 }
739
740 __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 if (!fold)
747 return NULL;
748 dup = qpolynomial_fold_alloc(fold->type,
749 isl_space_copy(fold->dim), fold->n);
750 if (!dup)
751 return NULL;
752
753 dup->n = fold->n;
754 for (i = 0; i < fold->n; ++i) {
755 dup->qp[i] = isl_qpolynomial_copy(fold->qp[i]);
756 if (!dup->qp[i])
757 goto error;
758 }
759
760 return dup;
761 error:
762 isl_qpolynomial_fold_free(dup);
763 return NULL;
764 }
765
766 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_cow(
767 __isl_take isl_qpolynomial_fold *fold)
768 {
769 if (!fold)
770 return NULL;
771
772 if (fold->ref == 1)
773 return fold;
774 fold->ref--;
775 return isl_qpolynomial_fold_dup(fold);
776 }
777
778 void isl_qpolynomial_fold_free(__isl_take isl_qpolynomial_fold *fold)
779 {
780 int i;
781
782 if (!fold)
783 return;
784 if (--fold->ref > 0)
785 return;
786
787 for (i = 0; i < fold->n; ++i)
788 isl_qpolynomial_free(fold->qp[i]);
789 isl_space_free(fold->dim);
790 free(fold);
791 }
792
793 int isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold *fold)
794 {
795 if (!fold)
796 return -1;
797
798 return fold->n == 0;
799 }
800
801 /* Does "fold" represent max(NaN) or min(NaN)?
802 */
803 isl_bool isl_qpolynomial_fold_is_nan(__isl_keep isl_qpolynomial_fold *fold)
804 {
805 if (!fold)
806 return isl_bool_error;
807 if (fold->n != 1)
808 return isl_bool_false;
809 return isl_qpolynomial_is_nan(fold->qp[0]);
810 }
811
812 __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 struct isl_qpolynomial_fold *res = NULL;
818
819 if (!fold1 || !fold2)
820 goto error;
821
822 isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error);
823 isl_assert(fold1->dim->ctx, isl_space_is_equal(fold1->dim, fold2->dim),
824 goto error);
825
826 if (isl_qpolynomial_fold_is_empty(fold1)) {
827 isl_qpolynomial_fold_free(fold1);
828 return fold2;
829 }
830
831 if (isl_qpolynomial_fold_is_empty(fold2)) {
832 isl_qpolynomial_fold_free(fold2);
833 return fold1;
834 }
835
836 res = qpolynomial_fold_alloc(fold1->type, isl_space_copy(fold1->dim),
837 fold1->n + fold2->n);
838 if (!res)
839 goto error;
840
841 for (i = 0; i < fold1->n; ++i) {
842 res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]);
843 if (!res->qp[res->n])
844 goto error;
845 res->n++;
846 }
847
848 for (i = 0; i < fold2->n; ++i) {
849 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
850 if (!res->qp[res->n])
851 goto error;
852 res->n++;
853 }
854
855 isl_qpolynomial_fold_free(fold1);
856 isl_qpolynomial_fold_free(fold2);
857
858 return res;
859 error:
860 isl_qpolynomial_fold_free(res);
861 isl_qpolynomial_fold_free(fold1);
862 isl_qpolynomial_fold_free(fold2);
863 return NULL;
864 }
865
866 __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 if (!pw1 || !pw2)
875 goto error;
876
877 isl_assert(pw1->dim->ctx, isl_space_is_equal(pw1->dim, pw2->dim), goto error);
878
879 if (isl_pw_qpolynomial_fold_is_zero(pw1)) {
880 isl_pw_qpolynomial_fold_free(pw1);
881 return pw2;
882 }
883
884 if (isl_pw_qpolynomial_fold_is_zero(pw2)) {
885 isl_pw_qpolynomial_fold_free(pw2);
886 return pw1;
887 }
888
889 if (pw1->type != pw2->type)
890 isl_die(pw1->dim->ctx, isl_error_invalid,
891 "fold types don't match", goto error);
892
893 n = (pw1->n + 1) * (pw2->n + 1);
894 res = isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pw1->dim),
895 pw1->type, n);
896
897 for (i = 0; i < pw1->n; ++i) {
898 set = isl_set_copy(pw1->p[i].set);
899 for (j = 0; j < pw2->n; ++j) {
900 struct isl_set *common;
901 isl_qpolynomial_fold *sum;
902 set = isl_set_subtract(set,
903 isl_set_copy(pw2->p[j].set));
904 common = isl_set_intersect(isl_set_copy(pw1->p[i].set),
905 isl_set_copy(pw2->p[j].set));
906 if (isl_set_plain_is_empty(common)) {
907 isl_set_free(common);
908 continue;
909 }
910
911 sum = isl_qpolynomial_fold_fold_on_domain(common,
912 isl_qpolynomial_fold_copy(pw1->p[i].fold),
913 isl_qpolynomial_fold_copy(pw2->p[j].fold));
914
915 res = isl_pw_qpolynomial_fold_add_piece(res, common, sum);
916 }
917 res = isl_pw_qpolynomial_fold_add_piece(res, set,
918 isl_qpolynomial_fold_copy(pw1->p[i].fold));
919 }
920
921 for (j = 0; j < pw2->n; ++j) {
922 set = isl_set_copy(pw2->p[j].set);
923 for (i = 0; i < pw1->n; ++i)
924 set = isl_set_subtract(set, isl_set_copy(pw1->p[i].set));
925 res = isl_pw_qpolynomial_fold_add_piece(res, set,
926 isl_qpolynomial_fold_copy(pw2->p[j].fold));
927 }
928
929 isl_pw_qpolynomial_fold_free(pw1);
930 isl_pw_qpolynomial_fold_free(pw2);
931
932 return res;
933 error:
934 isl_pw_qpolynomial_fold_free(pw1);
935 isl_pw_qpolynomial_fold_free(pw2);
936 return NULL;
937 }
938
939 __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 u = isl_union_pw_qpolynomial_fold_cow(u);
946
947 if (!part || !u)
948 goto error;
949 if (isl_space_check_equal_params(part->dim, u->space) < 0)
950 goto error;
951
952 entry = isl_union_pw_qpolynomial_fold_find_part_entry(u, part->dim, 1);
953 if (!entry)
954 goto error;
955
956 if (!entry->data)
957 entry->data = part;
958 else {
959 entry->data = isl_pw_qpolynomial_fold_fold(entry->data,
960 isl_pw_qpolynomial_fold_copy(part));
961 if (!entry->data)
962 goto error;
963 isl_pw_qpolynomial_fold_free(part);
964 }
965
966 return u;
967 error:
968 isl_pw_qpolynomial_fold_free(part);
969 isl_union_pw_qpolynomial_fold_free(u);
970 return NULL;
971 }
972
973 static isl_stat fold_part(__isl_take isl_pw_qpolynomial_fold *part, void *user)
974 {
975 isl_union_pw_qpolynomial_fold **u;
976 u = (isl_union_pw_qpolynomial_fold **)user;
977
978 *u = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(*u, part);
979
980 return isl_stat_ok;
981 }
982
983 __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 u1 = isl_union_pw_qpolynomial_fold_cow(u1);
988
989 if (!u1 || !u2)
990 goto error;
991
992 if (isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(u2,
993 &fold_part, &u1) < 0)
994 goto error;
995
996 isl_union_pw_qpolynomial_fold_free(u2);
997
998 return u1;
999 error:
1000 isl_union_pw_qpolynomial_fold_free(u1);
1001 isl_union_pw_qpolynomial_fold_free(u2);
1002 return NULL;
1003 }
1004
1005 __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 if (!pwqp)
1012 return NULL;
1013
1014 pwf = isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pwqp->dim),
1015 type, pwqp->n);
1016
1017 for (i = 0; i < pwqp->n; ++i)
1018 pwf = isl_pw_qpolynomial_fold_add_piece(pwf,
1019 isl_set_copy(pwqp->p[i].set),
1020 isl_qpolynomial_fold_alloc(type,
1021 isl_qpolynomial_copy(pwqp->p[i].qp)));
1022
1023 isl_pw_qpolynomial_free(pwqp);
1024
1025 return pwf;
1026 }
1027
1028 __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 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 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 if (fold1 == fold2)
1046 return 0;
1047 if (!fold1)
1048 return -1;
1049 if (!fold2)
1050 return 1;
1051
1052 if (fold1->n != fold2->n)
1053 return fold1->n - fold2->n;
1054
1055 for (i = 0; i < fold1->n; ++i) {
1056 int cmp;
1057
1058 cmp = isl_qpolynomial_plain_cmp(fold1->qp[i], fold2->qp[i]);
1059 if (cmp != 0)
1060 return cmp;
1061 }
1062
1063 return 0;
1064 }
1065
1066 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 if (!fold1 || !fold2)
1072 return -1;
1073
1074 if (fold1->n != fold2->n)
1075 return 0;
1076
1077 /* We probably want to sort the qps first... */
1078 for (i = 0; i < fold1->n; ++i) {
1079 int eq = isl_qpolynomial_plain_is_equal(fold1->qp[i], fold2->qp[i]);
1080 if (eq < 0 || !eq)
1081 return eq;
1082 }
1083
1084 return 1;
1085 }
1086
1087 __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 if (!fold || !pnt)
1094 goto error;
1095 ctx = isl_point_get_ctx(pnt);
1096 isl_assert(pnt->dim->ctx, isl_space_is_equal(pnt->dim, fold->dim), goto error);
1097 isl_assert(pnt->dim->ctx,
1098 fold->type == isl_fold_max || fold->type == isl_fold_min,
1099 goto error);
1100
1101 if (fold->n == 0)
1102 v = isl_val_zero(ctx);
1103 else {
1104 int i;
1105 v = isl_qpolynomial_eval(isl_qpolynomial_copy(fold->qp[0]),
1106 isl_point_copy(pnt));
1107 for (i = 1; i < fold->n; ++i) {
1108 isl_val *v_i;
1109 v_i = isl_qpolynomial_eval(
1110 isl_qpolynomial_copy(fold->qp[i]),
1111 isl_point_copy(pnt));
1112 if (fold->type == isl_fold_max)
1113 v = isl_val_max(v, v_i);
1114 else
1115 v = isl_val_min(v, v_i);
1116 }
1117 }
1118 isl_qpolynomial_fold_free(fold);
1119 isl_point_free(pnt);
1120
1121 return v;
1122 error:
1123 isl_qpolynomial_fold_free(fold);
1124 isl_point_free(pnt);
1125 return NULL;
1126 }
1127
1128 size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold *pwf)
1129 {
1130 int i;
1131 size_t n = 0;
1132
1133 for (i = 0; i < pwf->n; ++i)
1134 n += pwf->p[i].fold->n;
1135
1136 return n;
1137 }
1138
1139 __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 if (!set || !fold)
1146 goto error;
1147
1148 if (fold->n == 0) {
1149 opt = isl_val_zero(isl_set_get_ctx(set));
1150 isl_set_free(set);
1151 isl_qpolynomial_fold_free(fold);
1152 return opt;
1153 }
1154
1155 opt = isl_qpolynomial_opt_on_domain(isl_qpolynomial_copy(fold->qp[0]),
1156 isl_set_copy(set), max);
1157 for (i = 1; i < fold->n; ++i) {
1158 isl_val *opt_i;
1159 opt_i = isl_qpolynomial_opt_on_domain(
1160 isl_qpolynomial_copy(fold->qp[i]),
1161 isl_set_copy(set), max);
1162 if (max)
1163 opt = isl_val_max(opt, opt_i);
1164 else
1165 opt = isl_val_min(opt, opt_i);
1166 }
1167
1168 isl_set_free(set);
1169 isl_qpolynomial_fold_free(fold);
1170
1171 return opt;
1172 error:
1173 isl_set_free(set);
1174 isl_qpolynomial_fold_free(fold);
1175 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 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 if (!set || !fold1 || !fold2)
1189 return -1;
1190
1191 covers = fold1->type == isl_fold_max ? 1 : -1;
1192
1193 for (i = 0; i < fold2->n; ++i) {
1194 for (j = 0; j < fold1->n; ++j) {
1195 isl_qpolynomial *d;
1196 int sgn;
1197
1198 d = isl_qpolynomial_sub(
1199 isl_qpolynomial_copy(fold1->qp[j]),
1200 isl_qpolynomial_copy(fold2->qp[i]));
1201 sgn = isl_qpolynomial_sign(set, d);
1202 isl_qpolynomial_free(d);
1203 if (sgn == covers)
1204 break;
1205 }
1206 if (j >= fold1->n)
1207 return 0;
1208 }
1209
1210 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 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 if (!pwf1 || !pwf2)
1225 return -1;
1226
1227 if (pwf2->n == 0)
1228 return 1;
1229 if (pwf1->n == 0)
1230 return 0;
1231
1232 dom1 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1));
1233 dom2 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2));
1234 is_subset = isl_set_is_subset(dom2, dom1);
1235 isl_set_free(dom1);
1236 isl_set_free(dom2);
1237
1238 if (is_subset < 0 || !is_subset)
1239 return is_subset;
1240
1241 for (i = 0; i < pwf2->n; ++i) {
1242 for (j = 0; j < pwf1->n; ++j) {
1243 int is_empty;
1244 isl_set *common;
1245 int covers;
1246
1247 common = isl_set_intersect(isl_set_copy(pwf1->p[j].set),
1248 isl_set_copy(pwf2->p[i].set));
1249 is_empty = isl_set_is_empty(common);
1250 if (is_empty < 0 || is_empty) {
1251 isl_set_free(common);
1252 if (is_empty < 0)
1253 return -1;
1254 continue;
1255 }
1256 covers = qpolynomial_fold_covers_on_domain(common,
1257 pwf1->p[j].fold, pwf2->p[i].fold);
1258 isl_set_free(common);
1259 if (covers < 0 || !covers)
1260 return covers;
1261 }
1262 }
1263
1264 return 1;
1265 }
1266
1267 __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 if (!fold || !morph)
1274 goto error;
1275
1276 ctx = fold->dim->ctx;
1277 isl_assert(ctx, isl_space_is_equal(fold->dim, morph->dom->dim), goto error);
1278
1279 fold = isl_qpolynomial_fold_cow(fold);
1280 if (!fold)
1281 goto error;
1282
1283 isl_space_free(fold->dim);
1284 fold->dim = isl_space_copy(morph->ran->dim);
1285 if (!fold->dim)
1286 goto error;
1287
1288 for (i = 0; i < fold->n; ++i) {
1289 fold->qp[i] = isl_qpolynomial_morph_domain(fold->qp[i],
1290 isl_morph_copy(morph));
1291 if (!fold->qp[i])
1292 goto error;
1293 }
1294
1295 isl_morph_free(morph);
1296
1297 return fold;
1298 error:
1299 isl_qpolynomial_fold_free(fold);
1300 isl_morph_free(morph);
1301 return NULL;
1302 }
1303
1304 enum isl_fold isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold *fold)
1305 {
1306 if (!fold)
1307 return isl_fold_list;
1308 return fold->type;
1309 }
1310
1311 enum isl_fold isl_union_pw_qpolynomial_fold_get_type(
1312 __isl_keep isl_union_pw_qpolynomial_fold *upwf)
1313 {
1314 if (!upwf)
1315 return isl_fold_list;
1316 return upwf->type;
1317 }
1318
1319 __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 if (!fold || !dim)
1325 goto error;
1326
1327 if (isl_space_is_equal(fold->dim, dim)) {
1328 isl_space_free(dim);
1329 return fold;
1330 }
1331
1332 fold = isl_qpolynomial_fold_cow(fold);
1333 if (!fold)
1334 goto error;
1335
1336 isl_space_free(fold->dim);
1337 fold->dim = isl_space_copy(dim);
1338 if (!fold->dim)
1339 goto error;
1340
1341 for (i = 0; i < fold->n; ++i) {
1342 fold->qp[i] = isl_qpolynomial_lift(fold->qp[i],
1343 isl_space_copy(dim));
1344 if (!fold->qp[i])
1345 goto error;
1346 }
1347
1348 isl_space_free(dim);
1349
1350 return fold;
1351 error:
1352 isl_qpolynomial_fold_free(fold);
1353 isl_space_free(dim);
1354 return NULL;
1355 }
1356
1357 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 if (!fold)
1364 return isl_stat_error;
1365
1366 for (i = 0; i < fold->n; ++i)
1367 if (fn(isl_qpolynomial_copy(fold->qp[i]), user) < 0)
1368 return isl_stat_error;
1369
1370 return isl_stat_ok;
1371 }
1372
1373 __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 if (n == 0)
1382 return fold;
1383
1384 fold = isl_qpolynomial_fold_cow(fold);
1385 if (!fold)
1386 return NULL;
1387
1388 set_src_type = domain_type(src_type);
1389 set_dst_type = domain_type(dst_type);
1390
1391 fold->dim = isl_space_move_dims(fold->dim, set_dst_type, dst_pos,
1392 set_src_type, src_pos, n);
1393 if (!fold->dim)
1394 goto error;
1395
1396 for (i = 0; i < fold->n; ++i) {
1397 fold->qp[i] = isl_qpolynomial_move_dims(fold->qp[i],
1398 dst_type, dst_pos, src_type, src_pos, n);
1399 if (!fold->qp[i])
1400 goto error;
1401 }
1402
1403 return fold;
1404 error:
1405 isl_qpolynomial_fold_free(fold);
1406 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 __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 if (n == 0)
1420 return fold;
1421
1422 fold = isl_qpolynomial_fold_cow(fold);
1423 if (!fold)
1424 return NULL;
1425
1426 for (i = 0; i < fold->n; ++i) {
1427 fold->qp[i] = isl_qpolynomial_substitute(fold->qp[i],
1428 type, first, n, subs);
1429 if (!fold->qp[i])
1430 goto error;
1431 }
1432
1433 return fold;
1434 error:
1435 isl_qpolynomial_fold_free(fold);
1436 return NULL;
1437 }
1438
1439 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 upwf = (isl_union_pw_qpolynomial_fold **)user;
1446
1447 entry = isl_union_pw_qpolynomial_fold_find_part_entry(*upwf,
1448 pwqp->dim, 1);
1449 if (!entry)
1450 goto error;
1451
1452 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial((*upwf)->type, pwqp);
1453 if (!entry->data)
1454 entry->data = pwf;
1455 else {
1456 entry->data = isl_pw_qpolynomial_fold_add(entry->data, pwf);
1457 if (!entry->data)
1458 return isl_stat_error;
1459 if (isl_pw_qpolynomial_fold_is_zero(entry->data))
1460 *upwf = isl_union_pw_qpolynomial_fold_remove_part_entry(
1461 *upwf, entry);
1462 }
1463
1464 return isl_stat_ok;
1465 error:
1466 isl_pw_qpolynomial_free(pwqp);
1467 return isl_stat_error;
1468 }
1469
1470 __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 upwf = isl_union_pw_qpolynomial_fold_align_params(upwf,
1475 isl_union_pw_qpolynomial_get_space(upwqp));
1476 upwqp = isl_union_pw_qpolynomial_align_params(upwqp,
1477 isl_union_pw_qpolynomial_fold_get_space(upwf));
1478
1479 upwf = isl_union_pw_qpolynomial_fold_cow(upwf);
1480 if (!upwf || !upwqp)
1481 goto error;
1482
1483 if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp, &add_pwqp,
1484 &upwf) < 0)
1485 goto error;
1486
1487 isl_union_pw_qpolynomial_free(upwqp);
1488
1489 return upwf;
1490 error:
1491 isl_union_pw_qpolynomial_fold_free(upwf);
1492 isl_union_pw_qpolynomial_free(upwqp);
1493 return NULL;
1494 }
1495
1496 static isl_bool join_compatible(__isl_keep isl_space *space1,
1497 __isl_keep isl_space *space2)
1498 {
1499 isl_bool m;
1500 m = isl_space_has_equal_params(space1, space2);
1501 if (m < 0 || !m)
1502 return m;
1503 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 __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 ctx = isl_map_get_ctx(map);
1528 if (!ctx)
1529 goto error;
1530
1531 map_dim = isl_map_get_space(map);
1532 pwf_dim = isl_pw_qpolynomial_fold_get_space(pwf);
1533 ok = join_compatible(map_dim, pwf_dim);
1534 isl_space_free(map_dim);
1535 isl_space_free(pwf_dim);
1536 if (ok < 0)
1537 goto error;
1538 if (!ok)
1539 isl_die(ctx, isl_error_invalid, "incompatible dimensions",
1540 goto error);
1541
1542 n_in = isl_map_dim(map, isl_dim_in);
1543 pwf = isl_pw_qpolynomial_fold_insert_dims(pwf, isl_dim_in, 0, n_in);
1544
1545 dom = isl_map_wrap(map);
1546 pwf = isl_pw_qpolynomial_fold_reset_domain_space(pwf,
1547 isl_set_get_space(dom));
1548
1549 pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, dom);
1550 pwf = isl_pw_qpolynomial_fold_bound(pwf, tight);
1551
1552 return pwf;
1553 error:
1554 isl_map_free(map);
1555 isl_pw_qpolynomial_fold_free(pwf);
1556 return NULL;
1557 }
1558
1559 __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 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 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 struct isl_apply_fold_data *data = user;
1579 isl_bool ok;
1580
1581 map_dim = isl_map_get_space(data->map);
1582 pwf_dim = isl_pw_qpolynomial_fold_get_space(pwf);
1583 ok = join_compatible(map_dim, pwf_dim);
1584 isl_space_free(map_dim);
1585 isl_space_free(pwf_dim);
1586
1587 if (ok < 0)
1588 return isl_stat_error;
1589 if (ok) {
1590 pwf = isl_map_apply_pw_qpolynomial_fold(isl_map_copy(data->map),
1591 pwf, data->tight ? &data->tight : NULL);
1592 data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
1593 data->res, pwf);
1594 } else
1595 isl_pw_qpolynomial_fold_free(pwf);
1596
1597 return isl_stat_ok;
1598 }
1599
1600 static isl_stat map_apply(__isl_take isl_map *map, void *user)
1601 {
1602 struct isl_apply_fold_data *data = user;
1603 isl_stat r;
1604
1605 data->map = map;
1606 r = isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(
1607 data->upwf, &pw_qpolynomial_fold_apply, data);
1608
1609 isl_map_free(map);
1610 return r;
1611 }
1612
1613 __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 upwf = isl_union_pw_qpolynomial_fold_align_params(upwf,
1622 isl_union_map_get_space(umap));
1623 umap = isl_union_map_align_params(umap,
1624 isl_union_pw_qpolynomial_fold_get_space(upwf));
1625
1626 data.upwf = upwf;
1627 data.tight = tight ? 1 : 0;
1628 dim = isl_union_pw_qpolynomial_fold_get_space(upwf);
1629 type = isl_union_pw_qpolynomial_fold_get_type(upwf);
1630 data.res = isl_union_pw_qpolynomial_fold_zero(dim, type);
1631 if (isl_union_map_foreach_map(umap, &map_apply, &data) < 0)
1632 goto error;
1633
1634 isl_union_map_free(umap);
1635 isl_union_pw_qpolynomial_fold_free(upwf);
1636
1637 if (tight)
1638 *tight = data.tight;
1639
1640 return data.res;
1641 error:
1642 isl_union_map_free(umap);
1643 isl_union_pw_qpolynomial_fold_free(upwf);
1644 isl_union_pw_qpolynomial_fold_free(data.res);
1645 return NULL;
1646 }
1647
1648 __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 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 __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 fold = isl_qpolynomial_fold_cow(fold);
1664 if (!fold || !r)
1665 goto error;
1666
1667 for (i = 0; i < fold->n; ++i) {
1668 fold->qp[i] = isl_qpolynomial_realign_domain(fold->qp[i],
1669 isl_reordering_copy(r));
1670 if (!fold->qp[i])
1671 goto error;
1672 }
1673
1674 space = isl_reordering_get_space(r);
1675 fold = isl_qpolynomial_fold_reset_domain_space(fold, space);
1676
1677 isl_reordering_free(r);
1678
1679 return fold;
1680 error:
1681 isl_qpolynomial_fold_free(fold);
1682 isl_reordering_free(r);
1683 return NULL;
1684 }
1685
1686 __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 if (isl_int_is_one(v))
1692 return fold;
1693 if (fold && isl_int_is_zero(v)) {
1694 isl_qpolynomial_fold *zero;
1695 isl_space *dim = isl_space_copy(fold->dim);
1696 zero = isl_qpolynomial_fold_empty(fold->type, dim);
1697 isl_qpolynomial_fold_free(fold);
1698 return zero;
1699 }
1700
1701 fold = isl_qpolynomial_fold_cow(fold);
1702 if (!fold)
1703 return NULL;
1704
1705 if (isl_int_is_neg(v))
1706 fold->type = isl_fold_type_negate(fold->type);
1707 for (i = 0; i < fold->n; ++i) {
1708 fold->qp[i] = isl_qpolynomial_mul_isl_int(fold->qp[i], v);
1709 if (!fold->qp[i])
1710 goto error;
1711 }
1712
1713 return fold;
1714 error:
1715 isl_qpolynomial_fold_free(fold);
1716 return NULL;
1717 }
1718
1719 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale(
1720 __isl_take isl_qpolynomial_fold *fold, isl_int v)
1721 {
1722 return isl_qpolynomial_fold_mul_isl_int(fold, v);
1723 }
1724
1725 /* Multiply "fold" by "v".
1726 */
1727 __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 if (!fold || !v)
1733 goto error;
1734
1735 if (isl_val_is_one(v)) {
1736 isl_val_free(v);
1737 return fold;
1738 }
1739 if (isl_val_is_zero(v)) {
1740 isl_qpolynomial_fold *zero;
1741 isl_space *space = isl_qpolynomial_fold_get_domain_space(fold);
1742 zero = isl_qpolynomial_fold_empty(fold->type, space);
1743 isl_qpolynomial_fold_free(fold);
1744 isl_val_free(v);
1745 return zero;
1746 }
1747 if (!isl_val_is_rat(v))
1748 isl_die(isl_qpolynomial_fold_get_ctx(fold), isl_error_invalid,
1749 "expecting rational factor", goto error);
1750
1751 fold = isl_qpolynomial_fold_cow(fold);
1752 if (!fold)
1753 goto error;
1754
1755 if (isl_val_is_neg(v))
1756 fold->type = isl_fold_type_negate(fold->type);
1757 for (i = 0; i < fold->n; ++i) {
1758 fold->qp[i] = isl_qpolynomial_scale_val(fold->qp[i],
1759 isl_val_copy(v));
1760 if (!fold->qp[i])
1761 goto error;
1762 }
1763
1764 isl_val_free(v);
1765 return fold;
1766 error:
1767 isl_val_free(v);
1768 isl_qpolynomial_fold_free(fold);
1769 return NULL;
1770 }
1771
1772 /* Divide "fold" by "v".
1773 */
1774 __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 if (!fold || !v)
1778 goto error;
1779
1780 if (isl_val_is_one(v)) {
1781 isl_val_free(v);
1782 return fold;
1783 }
1784 if (!isl_val_is_rat(v))
1785 isl_die(isl_qpolynomial_fold_get_ctx(fold), isl_error_invalid,
1786 "expecting rational factor", goto error);
1787 if (isl_val_is_zero(v))
1788 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1789 "cannot scale down by zero", goto error);
1790
1791 return isl_qpolynomial_fold_scale_val(fold, isl_val_inv(v));
1792 error:
1793 isl_val_free(v);
1794 isl_qpolynomial_fold_free(fold);
1795 return NULL;
1796 }
Integer set library