?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_map_coalesce: eliminate unit divs from wrapping constraints
[isl.git] / isl_fold.c
blobaaa1b72793ab9c4c796ed7457a8329a9684fceec
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 *space)
96 {
97 int i;
98
99 fold = isl_qpolynomial_fold_cow(fold);
100 if (!fold || !space)
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(space));
106 if (!fold->qp[i])
107 goto error;
108 }
109
110 isl_space_free(fold->dim);
111 fold->dim = space;
112
113 return fold;
114 error:
115 isl_qpolynomial_fold_free(fold);
116 isl_space_free(space);
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 #include <isl_pw_templ.c>
703 #include <isl_pw_eval.c>
704 #include <isl_pw_insert_dims_templ.c>
705 #include <isl_pw_lift_templ.c>
706 #include <isl_pw_morph_templ.c>
707 #include <isl_pw_move_dims_templ.c>
708 #include <isl_pw_opt_templ.c>
709
710 #undef BASE
711 #define BASE pw_qpolynomial_fold
712
713 #define NO_SUB
714
715 #include <isl_union_single.c>
716 #include <isl_union_eval.c>
717
718 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_empty(enum isl_fold type,
719 __isl_take isl_space *space)
720 {
721 return qpolynomial_fold_alloc(type, space, 0);
722 }
723
724 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_alloc(
725 enum isl_fold type, __isl_take isl_qpolynomial *qp)
726 {
727 isl_qpolynomial_fold *fold;
728
729 if (!qp)
730 return NULL;
731
732 fold = qpolynomial_fold_alloc(type, isl_space_copy(qp->dim), 1);
733 if (!fold)
734 goto error;
735
736 fold->qp[0] = qp;
737 fold->n++;
738
739 return fold;
740 error:
741 isl_qpolynomial_fold_free(fold);
742 isl_qpolynomial_free(qp);
743 return NULL;
744 }
745
746 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_copy(
747 __isl_keep isl_qpolynomial_fold *fold)
748 {
749 if (!fold)
750 return NULL;
751
752 fold->ref++;
753 return fold;
754 }
755
756 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_dup(
757 __isl_keep isl_qpolynomial_fold *fold)
758 {
759 int i;
760 isl_qpolynomial_fold *dup;
761
762 if (!fold)
763 return NULL;
764 dup = qpolynomial_fold_alloc(fold->type,
765 isl_space_copy(fold->dim), fold->n);
766 if (!dup)
767 return NULL;
768
769 dup->n = fold->n;
770 for (i = 0; i < fold->n; ++i) {
771 dup->qp[i] = isl_qpolynomial_copy(fold->qp[i]);
772 if (!dup->qp[i])
773 goto error;
774 }
775
776 return dup;
777 error:
778 isl_qpolynomial_fold_free(dup);
779 return NULL;
780 }
781
782 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_cow(
783 __isl_take isl_qpolynomial_fold *fold)
784 {
785 if (!fold)
786 return NULL;
787
788 if (fold->ref == 1)
789 return fold;
790 fold->ref--;
791 return isl_qpolynomial_fold_dup(fold);
792 }
793
794 __isl_null isl_qpolynomial_fold *isl_qpolynomial_fold_free(
795 __isl_take isl_qpolynomial_fold *fold)
796 {
797 int i;
798
799 if (!fold)
800 return NULL;
801 if (--fold->ref > 0)
802 return NULL;
803
804 for (i = 0; i < fold->n; ++i)
805 isl_qpolynomial_free(fold->qp[i]);
806 isl_space_free(fold->dim);
807 free(fold);
808
809 return NULL;
810 }
811
812 isl_bool isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold *fold)
813 {
814 if (!fold)
815 return isl_bool_error;
816
817 return isl_bool_ok(fold->n == 0);
818 }
819
820 /* Does "fold" represent max(NaN) or min(NaN)?
821 */
822 isl_bool isl_qpolynomial_fold_is_nan(__isl_keep isl_qpolynomial_fold *fold)
823 {
824 if (!fold)
825 return isl_bool_error;
826 if (fold->n != 1)
827 return isl_bool_false;
828 return isl_qpolynomial_is_nan(fold->qp[0]);
829 }
830
831 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold(
832 __isl_take isl_qpolynomial_fold *fold1,
833 __isl_take isl_qpolynomial_fold *fold2)
834 {
835 int i;
836 struct isl_qpolynomial_fold *res = NULL;
837
838 if (!fold1 || !fold2)
839 goto error;
840
841 isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error);
842 isl_assert(fold1->dim->ctx, isl_space_is_equal(fold1->dim, fold2->dim),
843 goto error);
844
845 if (isl_qpolynomial_fold_is_empty(fold1)) {
846 isl_qpolynomial_fold_free(fold1);
847 return fold2;
848 }
849
850 if (isl_qpolynomial_fold_is_empty(fold2)) {
851 isl_qpolynomial_fold_free(fold2);
852 return fold1;
853 }
854
855 res = qpolynomial_fold_alloc(fold1->type, isl_space_copy(fold1->dim),
856 fold1->n + fold2->n);
857 if (!res)
858 goto error;
859
860 for (i = 0; i < fold1->n; ++i) {
861 res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]);
862 if (!res->qp[res->n])
863 goto error;
864 res->n++;
865 }
866
867 for (i = 0; i < fold2->n; ++i) {
868 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
869 if (!res->qp[res->n])
870 goto error;
871 res->n++;
872 }
873
874 isl_qpolynomial_fold_free(fold1);
875 isl_qpolynomial_fold_free(fold2);
876
877 return res;
878 error:
879 isl_qpolynomial_fold_free(res);
880 isl_qpolynomial_fold_free(fold1);
881 isl_qpolynomial_fold_free(fold2);
882 return NULL;
883 }
884
885 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_fold(
886 __isl_take isl_pw_qpolynomial_fold *pw1,
887 __isl_take isl_pw_qpolynomial_fold *pw2)
888 {
889 int i, j, n;
890 struct isl_pw_qpolynomial_fold *res;
891 isl_set *set;
892
893 if (!pw1 || !pw2)
894 goto error;
895
896 isl_assert(pw1->dim->ctx, isl_space_is_equal(pw1->dim, pw2->dim), goto error);
897
898 if (isl_pw_qpolynomial_fold_is_zero(pw1)) {
899 isl_pw_qpolynomial_fold_free(pw1);
900 return pw2;
901 }
902
903 if (isl_pw_qpolynomial_fold_is_zero(pw2)) {
904 isl_pw_qpolynomial_fold_free(pw2);
905 return pw1;
906 }
907
908 if (pw1->type != pw2->type)
909 isl_die(pw1->dim->ctx, isl_error_invalid,
910 "fold types don't match", goto error);
911
912 n = (pw1->n + 1) * (pw2->n + 1);
913 res = isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pw1->dim),
914 pw1->type, n);
915
916 for (i = 0; i < pw1->n; ++i) {
917 set = isl_set_copy(pw1->p[i].set);
918 for (j = 0; j < pw2->n; ++j) {
919 struct isl_set *common;
920 isl_qpolynomial_fold *sum;
921 set = isl_set_subtract(set,
922 isl_set_copy(pw2->p[j].set));
923 common = isl_set_intersect(isl_set_copy(pw1->p[i].set),
924 isl_set_copy(pw2->p[j].set));
925 if (isl_set_plain_is_empty(common)) {
926 isl_set_free(common);
927 continue;
928 }
929
930 sum = isl_qpolynomial_fold_fold_on_domain(common,
931 isl_qpolynomial_fold_copy(pw1->p[i].fold),
932 isl_qpolynomial_fold_copy(pw2->p[j].fold));
933
934 res = isl_pw_qpolynomial_fold_add_piece(res, common, sum);
935 }
936 res = isl_pw_qpolynomial_fold_add_piece(res, set,
937 isl_qpolynomial_fold_copy(pw1->p[i].fold));
938 }
939
940 for (j = 0; j < pw2->n; ++j) {
941 set = isl_set_copy(pw2->p[j].set);
942 for (i = 0; i < pw1->n; ++i)
943 set = isl_set_subtract(set, isl_set_copy(pw1->p[i].set));
944 res = isl_pw_qpolynomial_fold_add_piece(res, set,
945 isl_qpolynomial_fold_copy(pw2->p[j].fold));
946 }
947
948 isl_pw_qpolynomial_fold_free(pw1);
949 isl_pw_qpolynomial_fold_free(pw2);
950
951 return res;
952 error:
953 isl_pw_qpolynomial_fold_free(pw1);
954 isl_pw_qpolynomial_fold_free(pw2);
955 return NULL;
956 }
957
958 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
959 __isl_take isl_union_pw_qpolynomial_fold *u,
960 __isl_take isl_pw_qpolynomial_fold *part)
961 {
962 struct isl_hash_table_entry *entry;
963
964 u = isl_union_pw_qpolynomial_fold_cow(u);
965
966 if (!part || !u)
967 goto error;
968 if (isl_space_check_equal_params(part->dim, u->space) < 0)
969 goto error;
970
971 entry = isl_union_pw_qpolynomial_fold_find_part_entry(u, part->dim, 1);
972 if (!entry)
973 goto error;
974
975 if (!entry->data)
976 entry->data = part;
977 else {
978 entry->data = isl_pw_qpolynomial_fold_fold(entry->data,
979 isl_pw_qpolynomial_fold_copy(part));
980 if (!entry->data)
981 goto error;
982 isl_pw_qpolynomial_fold_free(part);
983 }
984
985 return u;
986 error:
987 isl_pw_qpolynomial_fold_free(part);
988 isl_union_pw_qpolynomial_fold_free(u);
989 return NULL;
990 }
991
992 static isl_stat fold_part(__isl_take isl_pw_qpolynomial_fold *part, void *user)
993 {
994 isl_union_pw_qpolynomial_fold **u;
995 u = (isl_union_pw_qpolynomial_fold **)user;
996
997 *u = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(*u, part);
998
999 return isl_stat_ok;
1000 }
1001
1002 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold(
1003 __isl_take isl_union_pw_qpolynomial_fold *u1,
1004 __isl_take isl_union_pw_qpolynomial_fold *u2)
1005 {
1006 u1 = isl_union_pw_qpolynomial_fold_cow(u1);
1007
1008 if (!u1 || !u2)
1009 goto error;
1010
1011 if (isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(u2,
1012 &fold_part, &u1) < 0)
1013 goto error;
1014
1015 isl_union_pw_qpolynomial_fold_free(u2);
1016
1017 return u1;
1018 error:
1019 isl_union_pw_qpolynomial_fold_free(u1);
1020 isl_union_pw_qpolynomial_fold_free(u2);
1021 return NULL;
1022 }
1023
1024 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_from_pw_qpolynomial(
1025 enum isl_fold type, __isl_take isl_pw_qpolynomial *pwqp)
1026 {
1027 int i;
1028 isl_pw_qpolynomial_fold *pwf;
1029
1030 if (!pwqp)
1031 return NULL;
1032
1033 pwf = isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pwqp->dim),
1034 type, pwqp->n);
1035
1036 for (i = 0; i < pwqp->n; ++i)
1037 pwf = isl_pw_qpolynomial_fold_add_piece(pwf,
1038 isl_set_copy(pwqp->p[i].set),
1039 isl_qpolynomial_fold_alloc(type,
1040 isl_qpolynomial_copy(pwqp->p[i].qp)));
1041
1042 isl_pw_qpolynomial_free(pwqp);
1043
1044 return pwf;
1045 }
1046
1047 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_add(
1048 __isl_take isl_pw_qpolynomial_fold *pwf1,
1049 __isl_take isl_pw_qpolynomial_fold *pwf2)
1050 {
1051 return isl_pw_qpolynomial_fold_union_add_(pwf1, pwf2);
1052 }
1053
1054 /* Compare two quasi-polynomial reductions.
1055 *
1056 * Return -1 if "fold1" is "smaller" than "fold2", 1 if "fold1" is "greater"
1057 * than "fold2" and 0 if they are equal.
1058 */
1059 int isl_qpolynomial_fold_plain_cmp(__isl_keep isl_qpolynomial_fold *fold1,
1060 __isl_keep isl_qpolynomial_fold *fold2)
1061 {
1062 int i;
1063
1064 if (fold1 == fold2)
1065 return 0;
1066 if (!fold1)
1067 return -1;
1068 if (!fold2)
1069 return 1;
1070
1071 if (fold1->n != fold2->n)
1072 return fold1->n - fold2->n;
1073
1074 for (i = 0; i < fold1->n; ++i) {
1075 int cmp;
1076
1077 cmp = isl_qpolynomial_plain_cmp(fold1->qp[i], fold2->qp[i]);
1078 if (cmp != 0)
1079 return cmp;
1080 }
1081
1082 return 0;
1083 }
1084
1085 int isl_qpolynomial_fold_plain_is_equal(__isl_keep isl_qpolynomial_fold *fold1,
1086 __isl_keep isl_qpolynomial_fold *fold2)
1087 {
1088 int i;
1089
1090 if (!fold1 || !fold2)
1091 return -1;
1092
1093 if (fold1->n != fold2->n)
1094 return 0;
1095
1096 /* We probably want to sort the qps first... */
1097 for (i = 0; i < fold1->n; ++i) {
1098 int eq = isl_qpolynomial_plain_is_equal(fold1->qp[i], fold2->qp[i]);
1099 if (eq < 0 || !eq)
1100 return eq;
1101 }
1102
1103 return 1;
1104 }
1105
1106 __isl_give isl_val *isl_qpolynomial_fold_eval(
1107 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_point *pnt)
1108 {
1109 isl_ctx *ctx;
1110 isl_val *v;
1111
1112 if (!fold || !pnt)
1113 goto error;
1114 ctx = isl_point_get_ctx(pnt);
1115 isl_assert(pnt->dim->ctx, isl_space_is_equal(pnt->dim, fold->dim), goto error);
1116 isl_assert(pnt->dim->ctx,
1117 fold->type == isl_fold_max || fold->type == isl_fold_min,
1118 goto error);
1119
1120 if (fold->n == 0)
1121 v = isl_val_zero(ctx);
1122 else {
1123 int i;
1124 v = isl_qpolynomial_eval(isl_qpolynomial_copy(fold->qp[0]),
1125 isl_point_copy(pnt));
1126 for (i = 1; i < fold->n; ++i) {
1127 isl_val *v_i;
1128 v_i = isl_qpolynomial_eval(
1129 isl_qpolynomial_copy(fold->qp[i]),
1130 isl_point_copy(pnt));
1131 if (fold->type == isl_fold_max)
1132 v = isl_val_max(v, v_i);
1133 else
1134 v = isl_val_min(v, v_i);
1135 }
1136 }
1137 isl_qpolynomial_fold_free(fold);
1138 isl_point_free(pnt);
1139
1140 return v;
1141 error:
1142 isl_qpolynomial_fold_free(fold);
1143 isl_point_free(pnt);
1144 return NULL;
1145 }
1146
1147 size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold *pwf)
1148 {
1149 int i;
1150 size_t n = 0;
1151
1152 for (i = 0; i < pwf->n; ++i)
1153 n += pwf->p[i].fold->n;
1154
1155 return n;
1156 }
1157
1158 __isl_give isl_val *isl_qpolynomial_fold_opt_on_domain(
1159 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *set, int max)
1160 {
1161 int i;
1162 isl_val *opt;
1163
1164 if (!set || !fold)
1165 goto error;
1166
1167 if (fold->n == 0) {
1168 opt = isl_val_zero(isl_set_get_ctx(set));
1169 isl_set_free(set);
1170 isl_qpolynomial_fold_free(fold);
1171 return opt;
1172 }
1173
1174 opt = isl_qpolynomial_opt_on_domain(isl_qpolynomial_copy(fold->qp[0]),
1175 isl_set_copy(set), max);
1176 for (i = 1; i < fold->n; ++i) {
1177 isl_val *opt_i;
1178 opt_i = isl_qpolynomial_opt_on_domain(
1179 isl_qpolynomial_copy(fold->qp[i]),
1180 isl_set_copy(set), max);
1181 if (max)
1182 opt = isl_val_max(opt, opt_i);
1183 else
1184 opt = isl_val_min(opt, opt_i);
1185 }
1186
1187 isl_set_free(set);
1188 isl_qpolynomial_fold_free(fold);
1189
1190 return opt;
1191 error:
1192 isl_set_free(set);
1193 isl_qpolynomial_fold_free(fold);
1194 return NULL;
1195 }
1196
1197 /* Check whether for each quasi-polynomial in "fold2" there is
1198 * a quasi-polynomial in "fold1" that dominates it on "set".
1199 */
1200 static isl_bool qpolynomial_fold_covers_on_domain(__isl_keep isl_set *set,
1201 __isl_keep isl_qpolynomial_fold *fold1,
1202 __isl_keep isl_qpolynomial_fold *fold2)
1203 {
1204 int i, j;
1205 int covers;
1206
1207 if (!set || !fold1 || !fold2)
1208 return isl_bool_error;
1209
1210 covers = fold1->type == isl_fold_max ? 1 : -1;
1211
1212 for (i = 0; i < fold2->n; ++i) {
1213 for (j = 0; j < fold1->n; ++j) {
1214 isl_qpolynomial *d;
1215 int sgn;
1216
1217 d = isl_qpolynomial_sub(
1218 isl_qpolynomial_copy(fold1->qp[j]),
1219 isl_qpolynomial_copy(fold2->qp[i]));
1220 sgn = isl_qpolynomial_sign(set, d);
1221 isl_qpolynomial_free(d);
1222 if (sgn == covers)
1223 break;
1224 }
1225 if (j >= fold1->n)
1226 return isl_bool_false;
1227 }
1228
1229 return isl_bool_true;
1230 }
1231
1232 /* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains
1233 * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates
1234 * that of pwf2.
1235 */
1236 isl_bool isl_pw_qpolynomial_fold_covers(
1237 __isl_keep isl_pw_qpolynomial_fold *pwf1,
1238 __isl_keep isl_pw_qpolynomial_fold *pwf2)
1239 {
1240 int i, j;
1241 isl_set *dom1, *dom2;
1242 isl_bool is_subset;
1243
1244 if (!pwf1 || !pwf2)
1245 return isl_bool_error;
1246
1247 if (pwf2->n == 0)
1248 return isl_bool_true;
1249 if (pwf1->n == 0)
1250 return isl_bool_false;
1251
1252 dom1 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1));
1253 dom2 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2));
1254 is_subset = isl_set_is_subset(dom2, dom1);
1255 isl_set_free(dom1);
1256 isl_set_free(dom2);
1257
1258 if (is_subset < 0 || !is_subset)
1259 return is_subset;
1260
1261 for (i = 0; i < pwf2->n; ++i) {
1262 for (j = 0; j < pwf1->n; ++j) {
1263 isl_bool is_empty;
1264 isl_set *common;
1265 isl_bool covers;
1266
1267 common = isl_set_intersect(isl_set_copy(pwf1->p[j].set),
1268 isl_set_copy(pwf2->p[i].set));
1269 is_empty = isl_set_is_empty(common);
1270 if (is_empty < 0 || is_empty) {
1271 isl_set_free(common);
1272 if (is_empty < 0)
1273 return isl_bool_error;
1274 continue;
1275 }
1276 covers = qpolynomial_fold_covers_on_domain(common,
1277 pwf1->p[j].fold, pwf2->p[i].fold);
1278 isl_set_free(common);
1279 if (covers < 0 || !covers)
1280 return covers;
1281 }
1282 }
1283
1284 return isl_bool_true;
1285 }
1286
1287 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_morph_domain(
1288 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_morph *morph)
1289 {
1290 int i;
1291 isl_ctx *ctx;
1292
1293 if (!fold || !morph)
1294 goto error;
1295
1296 ctx = fold->dim->ctx;
1297 isl_assert(ctx, isl_space_is_equal(fold->dim, morph->dom->dim), goto error);
1298
1299 fold = isl_qpolynomial_fold_cow(fold);
1300 if (!fold)
1301 goto error;
1302
1303 isl_space_free(fold->dim);
1304 fold->dim = isl_space_copy(morph->ran->dim);
1305 if (!fold->dim)
1306 goto error;
1307
1308 for (i = 0; i < fold->n; ++i) {
1309 fold->qp[i] = isl_qpolynomial_morph_domain(fold->qp[i],
1310 isl_morph_copy(morph));
1311 if (!fold->qp[i])
1312 goto error;
1313 }
1314
1315 isl_morph_free(morph);
1316
1317 return fold;
1318 error:
1319 isl_qpolynomial_fold_free(fold);
1320 isl_morph_free(morph);
1321 return NULL;
1322 }
1323
1324 enum isl_fold isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold *fold)
1325 {
1326 if (!fold)
1327 return isl_fold_error;
1328 return fold->type;
1329 }
1330
1331 /* Return the type of this piecewise quasipolynomial reduction.
1332 */
1333 enum isl_fold isl_pw_qpolynomial_fold_get_type(
1334 __isl_keep isl_pw_qpolynomial_fold *pwf)
1335 {
1336 if (!pwf)
1337 return isl_fold_error;
1338 return pwf->type;
1339 }
1340
1341 enum isl_fold isl_union_pw_qpolynomial_fold_get_type(
1342 __isl_keep isl_union_pw_qpolynomial_fold *upwf)
1343 {
1344 if (!upwf)
1345 return isl_fold_error;
1346 return upwf->type;
1347 }
1348
1349 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_lift(
1350 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_space *space)
1351 {
1352 int i;
1353
1354 if (!fold || !space)
1355 goto error;
1356
1357 if (isl_space_is_equal(fold->dim, space)) {
1358 isl_space_free(space);
1359 return fold;
1360 }
1361
1362 fold = isl_qpolynomial_fold_cow(fold);
1363 if (!fold)
1364 goto error;
1365
1366 isl_space_free(fold->dim);
1367 fold->dim = isl_space_copy(space);
1368 if (!fold->dim)
1369 goto error;
1370
1371 for (i = 0; i < fold->n; ++i) {
1372 fold->qp[i] = isl_qpolynomial_lift(fold->qp[i],
1373 isl_space_copy(space));
1374 if (!fold->qp[i])
1375 goto error;
1376 }
1377
1378 isl_space_free(space);
1379
1380 return fold;
1381 error:
1382 isl_qpolynomial_fold_free(fold);
1383 isl_space_free(space);
1384 return NULL;
1385 }
1386
1387 isl_stat isl_qpolynomial_fold_foreach_qpolynomial(
1388 __isl_keep isl_qpolynomial_fold *fold,
1389 isl_stat (*fn)(__isl_take isl_qpolynomial *qp, void *user), void *user)
1390 {
1391 int i;
1392
1393 if (!fold)
1394 return isl_stat_error;
1395
1396 for (i = 0; i < fold->n; ++i)
1397 if (fn(isl_qpolynomial_copy(fold->qp[i]), user) < 0)
1398 return isl_stat_error;
1399
1400 return isl_stat_ok;
1401 }
1402
1403 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_move_dims(
1404 __isl_take isl_qpolynomial_fold *fold,
1405 enum isl_dim_type dst_type, unsigned dst_pos,
1406 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1407 {
1408 int i;
1409 enum isl_dim_type set_src_type, set_dst_type;
1410
1411 if (n == 0)
1412 return fold;
1413
1414 fold = isl_qpolynomial_fold_cow(fold);
1415 if (!fold)
1416 return NULL;
1417
1418 set_src_type = domain_type(src_type);
1419 set_dst_type = domain_type(dst_type);
1420
1421 fold->dim = isl_space_move_dims(fold->dim, set_dst_type, dst_pos,
1422 set_src_type, src_pos, n);
1423 if (!fold->dim)
1424 goto error;
1425
1426 for (i = 0; i < fold->n; ++i) {
1427 fold->qp[i] = isl_qpolynomial_move_dims(fold->qp[i],
1428 dst_type, dst_pos, src_type, src_pos, n);
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 /* For each 0 <= i < "n", replace variable "first" + i of type "type"
1440 * in fold->qp[k] by subs[i].
1441 */
1442 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute(
1443 __isl_take isl_qpolynomial_fold *fold,
1444 enum isl_dim_type type, unsigned first, unsigned n,
1445 __isl_keep isl_qpolynomial **subs)
1446 {
1447 int i;
1448
1449 if (n == 0)
1450 return fold;
1451
1452 fold = isl_qpolynomial_fold_cow(fold);
1453 if (!fold)
1454 return NULL;
1455
1456 for (i = 0; i < fold->n; ++i) {
1457 fold->qp[i] = isl_qpolynomial_substitute(fold->qp[i],
1458 type, first, n, subs);
1459 if (!fold->qp[i])
1460 goto error;
1461 }
1462
1463 return fold;
1464 error:
1465 isl_qpolynomial_fold_free(fold);
1466 return NULL;
1467 }
1468
1469 static isl_stat add_pwqp(__isl_take isl_pw_qpolynomial *pwqp, void *user)
1470 {
1471 isl_pw_qpolynomial_fold *pwf;
1472 isl_union_pw_qpolynomial_fold **upwf;
1473 struct isl_hash_table_entry *entry;
1474
1475 upwf = (isl_union_pw_qpolynomial_fold **)user;
1476
1477 entry = isl_union_pw_qpolynomial_fold_find_part_entry(*upwf,
1478 pwqp->dim, 1);
1479 if (!entry)
1480 goto error;
1481
1482 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial((*upwf)->type, pwqp);
1483 if (!entry->data)
1484 entry->data = pwf;
1485 else {
1486 entry->data = isl_pw_qpolynomial_fold_add(entry->data, pwf);
1487 if (!entry->data)
1488 return isl_stat_error;
1489 if (isl_pw_qpolynomial_fold_is_zero(entry->data))
1490 *upwf = isl_union_pw_qpolynomial_fold_remove_part_entry(
1491 *upwf, entry);
1492 }
1493
1494 return isl_stat_ok;
1495 error:
1496 isl_pw_qpolynomial_free(pwqp);
1497 return isl_stat_error;
1498 }
1499
1500 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial(
1501 __isl_take isl_union_pw_qpolynomial_fold *upwf,
1502 __isl_take isl_union_pw_qpolynomial *upwqp)
1503 {
1504 upwf = isl_union_pw_qpolynomial_fold_align_params(upwf,
1505 isl_union_pw_qpolynomial_get_space(upwqp));
1506 upwqp = isl_union_pw_qpolynomial_align_params(upwqp,
1507 isl_union_pw_qpolynomial_fold_get_space(upwf));
1508
1509 upwf = isl_union_pw_qpolynomial_fold_cow(upwf);
1510 if (!upwf || !upwqp)
1511 goto error;
1512
1513 if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp, &add_pwqp,
1514 &upwf) < 0)
1515 goto error;
1516
1517 isl_union_pw_qpolynomial_free(upwqp);
1518
1519 return upwf;
1520 error:
1521 isl_union_pw_qpolynomial_fold_free(upwf);
1522 isl_union_pw_qpolynomial_free(upwqp);
1523 return NULL;
1524 }
1525
1526 static isl_bool join_compatible(__isl_keep isl_space *space1,
1527 __isl_keep isl_space *space2)
1528 {
1529 isl_bool m;
1530 m = isl_space_has_equal_params(space1, space2);
1531 if (m < 0 || !m)
1532 return m;
1533 return isl_space_tuple_is_equal(space1, isl_dim_out,
1534 space2, isl_dim_in);
1535 }
1536
1537 /* Compute the intersection of the range of the map and the domain
1538 * of the piecewise quasipolynomial reduction and then compute a bound
1539 * on the associated quasipolynomial reduction over all elements
1540 * in this intersection.
1541 *
1542 * We first introduce some unconstrained dimensions in the
1543 * piecewise quasipolynomial, intersect the resulting domain
1544 * with the wrapped map and the compute the sum.
1545 */
1546 __isl_give isl_pw_qpolynomial_fold *isl_map_apply_pw_qpolynomial_fold(
1547 __isl_take isl_map *map, __isl_take isl_pw_qpolynomial_fold *pwf,
1548 isl_bool *tight)
1549 {
1550 isl_ctx *ctx;
1551 isl_set *dom;
1552 isl_space *map_space;
1553 isl_space *pwf_space;
1554 isl_size n_in;
1555 isl_bool ok;
1556
1557 ctx = isl_map_get_ctx(map);
1558 if (!ctx)
1559 goto error;
1560
1561 map_space = isl_map_get_space(map);
1562 pwf_space = isl_pw_qpolynomial_fold_get_space(pwf);
1563 ok = join_compatible(map_space, pwf_space);
1564 isl_space_free(map_space);
1565 isl_space_free(pwf_space);
1566 if (ok < 0)
1567 goto error;
1568 if (!ok)
1569 isl_die(ctx, isl_error_invalid, "incompatible dimensions",
1570 goto error);
1571
1572 n_in = isl_map_dim(map, isl_dim_in);
1573 if (n_in < 0)
1574 goto error;
1575 pwf = isl_pw_qpolynomial_fold_insert_dims(pwf, isl_dim_in, 0, n_in);
1576
1577 dom = isl_map_wrap(map);
1578 pwf = isl_pw_qpolynomial_fold_reset_domain_space(pwf,
1579 isl_set_get_space(dom));
1580
1581 pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, dom);
1582 pwf = isl_pw_qpolynomial_fold_bound(pwf, tight);
1583
1584 return pwf;
1585 error:
1586 isl_map_free(map);
1587 isl_pw_qpolynomial_fold_free(pwf);
1588 return NULL;
1589 }
1590
1591 __isl_give isl_pw_qpolynomial_fold *isl_set_apply_pw_qpolynomial_fold(
1592 __isl_take isl_set *set, __isl_take isl_pw_qpolynomial_fold *pwf,
1593 isl_bool *tight)
1594 {
1595 return isl_map_apply_pw_qpolynomial_fold(set, pwf, tight);
1596 }
1597
1598 struct isl_apply_fold_data {
1599 isl_union_pw_qpolynomial_fold *upwf;
1600 isl_union_pw_qpolynomial_fold *res;
1601 isl_map *map;
1602 isl_bool tight;
1603 };
1604
1605 static isl_stat pw_qpolynomial_fold_apply(
1606 __isl_take isl_pw_qpolynomial_fold *pwf, void *user)
1607 {
1608 isl_space *map_dim;
1609 isl_space *pwf_dim;
1610 struct isl_apply_fold_data *data = user;
1611 isl_bool ok;
1612
1613 map_dim = isl_map_get_space(data->map);
1614 pwf_dim = isl_pw_qpolynomial_fold_get_space(pwf);
1615 ok = join_compatible(map_dim, pwf_dim);
1616 isl_space_free(map_dim);
1617 isl_space_free(pwf_dim);
1618
1619 if (ok < 0)
1620 return isl_stat_error;
1621 if (ok) {
1622 pwf = isl_map_apply_pw_qpolynomial_fold(isl_map_copy(data->map),
1623 pwf, data->tight ? &data->tight : NULL);
1624 data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
1625 data->res, pwf);
1626 } else
1627 isl_pw_qpolynomial_fold_free(pwf);
1628
1629 return isl_stat_ok;
1630 }
1631
1632 static isl_stat map_apply(__isl_take isl_map *map, void *user)
1633 {
1634 struct isl_apply_fold_data *data = user;
1635 isl_stat r;
1636
1637 data->map = map;
1638 r = isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(
1639 data->upwf, &pw_qpolynomial_fold_apply, data);
1640
1641 isl_map_free(map);
1642 return r;
1643 }
1644
1645 __isl_give isl_union_pw_qpolynomial_fold *isl_union_map_apply_union_pw_qpolynomial_fold(
1646 __isl_take isl_union_map *umap,
1647 __isl_take isl_union_pw_qpolynomial_fold *upwf, isl_bool *tight)
1648 {
1649 isl_space *space;
1650 enum isl_fold type;
1651 struct isl_apply_fold_data data;
1652
1653 upwf = isl_union_pw_qpolynomial_fold_align_params(upwf,
1654 isl_union_map_get_space(umap));
1655 umap = isl_union_map_align_params(umap,
1656 isl_union_pw_qpolynomial_fold_get_space(upwf));
1657
1658 data.upwf = upwf;
1659 data.tight = tight ? isl_bool_true : isl_bool_false;
1660 space = isl_union_pw_qpolynomial_fold_get_space(upwf);
1661 type = isl_union_pw_qpolynomial_fold_get_type(upwf);
1662 data.res = isl_union_pw_qpolynomial_fold_zero(space, type);
1663 if (isl_union_map_foreach_map(umap, &map_apply, &data) < 0)
1664 goto error;
1665
1666 isl_union_map_free(umap);
1667 isl_union_pw_qpolynomial_fold_free(upwf);
1668
1669 if (tight)
1670 *tight = data.tight;
1671
1672 return data.res;
1673 error:
1674 isl_union_map_free(umap);
1675 isl_union_pw_qpolynomial_fold_free(upwf);
1676 isl_union_pw_qpolynomial_fold_free(data.res);
1677 return NULL;
1678 }
1679
1680 __isl_give isl_union_pw_qpolynomial_fold *isl_union_set_apply_union_pw_qpolynomial_fold(
1681 __isl_take isl_union_set *uset,
1682 __isl_take isl_union_pw_qpolynomial_fold *upwf, isl_bool *tight)
1683 {
1684 return isl_union_map_apply_union_pw_qpolynomial_fold(uset, upwf, tight);
1685 }
1686
1687 /* Reorder the dimension of "fold" according to the given reordering.
1688 */
1689 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_realign_domain(
1690 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_reordering *r)
1691 {
1692 int i;
1693 isl_space *space;
1694
1695 fold = isl_qpolynomial_fold_cow(fold);
1696 if (!fold || !r)
1697 goto error;
1698
1699 for (i = 0; i < fold->n; ++i) {
1700 fold->qp[i] = isl_qpolynomial_realign_domain(fold->qp[i],
1701 isl_reordering_copy(r));
1702 if (!fold->qp[i])
1703 goto error;
1704 }
1705
1706 space = isl_reordering_get_space(r);
1707 fold = isl_qpolynomial_fold_reset_domain_space(fold, space);
1708
1709 isl_reordering_free(r);
1710
1711 return fold;
1712 error:
1713 isl_qpolynomial_fold_free(fold);
1714 isl_reordering_free(r);
1715 return NULL;
1716 }
1717
1718 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_mul_isl_int(
1719 __isl_take isl_qpolynomial_fold *fold, isl_int v)
1720 {
1721 int i;
1722
1723 if (isl_int_is_one(v))
1724 return fold;
1725 if (fold && isl_int_is_zero(v)) {
1726 isl_qpolynomial_fold *zero;
1727 isl_space *space = isl_space_copy(fold->dim);
1728 zero = isl_qpolynomial_fold_empty(fold->type, space);
1729 isl_qpolynomial_fold_free(fold);
1730 return zero;
1731 }
1732
1733 fold = isl_qpolynomial_fold_cow(fold);
1734 if (!fold)
1735 return NULL;
1736
1737 if (isl_int_is_neg(v))
1738 fold->type = isl_fold_type_negate(fold->type);
1739 for (i = 0; i < fold->n; ++i) {
1740 fold->qp[i] = isl_qpolynomial_mul_isl_int(fold->qp[i], v);
1741 if (!fold->qp[i])
1742 goto error;
1743 }
1744
1745 return fold;
1746 error:
1747 isl_qpolynomial_fold_free(fold);
1748 return NULL;
1749 }
1750
1751 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale(
1752 __isl_take isl_qpolynomial_fold *fold, isl_int v)
1753 {
1754 return isl_qpolynomial_fold_mul_isl_int(fold, v);
1755 }
1756
1757 /* Multiply "fold" by "v".
1758 */
1759 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale_val(
1760 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_val *v)
1761 {
1762 int i;
1763
1764 if (!fold || !v)
1765 goto error;
1766
1767 if (isl_val_is_one(v)) {
1768 isl_val_free(v);
1769 return fold;
1770 }
1771 if (isl_val_is_zero(v)) {
1772 isl_qpolynomial_fold *zero;
1773 isl_space *space = isl_qpolynomial_fold_get_domain_space(fold);
1774 zero = isl_qpolynomial_fold_empty(fold->type, space);
1775 isl_qpolynomial_fold_free(fold);
1776 isl_val_free(v);
1777 return zero;
1778 }
1779 if (!isl_val_is_rat(v))
1780 isl_die(isl_qpolynomial_fold_get_ctx(fold), isl_error_invalid,
1781 "expecting rational factor", goto error);
1782
1783 fold = isl_qpolynomial_fold_cow(fold);
1784 if (!fold)
1785 goto error;
1786
1787 if (isl_val_is_neg(v))
1788 fold->type = isl_fold_type_negate(fold->type);
1789 for (i = 0; i < fold->n; ++i) {
1790 fold->qp[i] = isl_qpolynomial_scale_val(fold->qp[i],
1791 isl_val_copy(v));
1792 if (!fold->qp[i])
1793 goto error;
1794 }
1795
1796 isl_val_free(v);
1797 return fold;
1798 error:
1799 isl_val_free(v);
1800 isl_qpolynomial_fold_free(fold);
1801 return NULL;
1802 }
1803
1804 /* Divide "fold" by "v".
1805 */
1806 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale_down_val(
1807 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_val *v)
1808 {
1809 if (!fold || !v)
1810 goto error;
1811
1812 if (isl_val_is_one(v)) {
1813 isl_val_free(v);
1814 return fold;
1815 }
1816 if (!isl_val_is_rat(v))
1817 isl_die(isl_qpolynomial_fold_get_ctx(fold), isl_error_invalid,
1818 "expecting rational factor", goto error);
1819 if (isl_val_is_zero(v))
1820 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1821 "cannot scale down by zero", goto error);
1822
1823 return isl_qpolynomial_fold_scale_val(fold, isl_val_inv(v));
1824 error:
1825 isl_val_free(v);
1826 isl_qpolynomial_fold_free(fold);
1827 return NULL;
1828 }
Integer set library