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