?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Merge branch 'maint'
[isl.git] / isl_fold.c
blob57e7af5a5d84dcdbab8d519ed7519327a0404578
1 /*
2 * Copyright 2010 INRIA Saclay
3 *
4 * Use of this software is governed by the GNU LGPLv2.1 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_union_map_private.h>
12 #include <isl_polynomial_private.h>
13 #include <isl_point_private.h>
14 #include <isl_dim_private.h>
15 #include <isl_map_private.h>
16 #include <isl/lp.h>
17 #include <isl/seq.h>
18 #include <isl_mat_private.h>
19
20 static __isl_give isl_qpolynomial_fold *qpolynomial_fold_alloc(
21 enum isl_fold type, __isl_take isl_dim *dim, int n)
22 {
23 isl_qpolynomial_fold *fold;
24
25 if (!dim)
26 goto error;
27
28 isl_assert(dim->ctx, n >= 0, goto error);
29 fold = isl_calloc(dim->ctx, struct isl_qpolynomial_fold,
30 sizeof(struct isl_qpolynomial_fold) +
31 (n - 1) * sizeof(struct isl_qpolynomial *));
32 if (!fold)
33 goto error;
34
35 fold->ref = 1;
36 fold->size = n;
37 fold->n = 0;
38 fold->type = type;
39 fold->dim = dim;
40
41 return fold;
42 error:
43 isl_dim_free(dim);
44 return NULL;
45 }
46
47 isl_ctx *isl_qpolynomial_fold_get_ctx(__isl_keep isl_qpolynomial_fold *fold)
48 {
49 return fold ? fold->dim->ctx : NULL;
50 }
51
52 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_reset_dim(
53 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_dim *dim)
54 {
55 int i;
56
57 fold = isl_qpolynomial_fold_cow(fold);
58 if (!fold || !dim)
59 goto error;
60
61 for (i = 0; i < fold->n; ++i) {
62 fold->qp[i] = isl_qpolynomial_reset_dim(fold->qp[i],
63 isl_dim_copy(dim));
64 if (!fold->qp[i])
65 goto error;
66 }
67
68 isl_dim_free(fold->dim);
69 fold->dim = dim;
70
71 return fold;
72 error:
73 isl_qpolynomial_fold_free(fold);
74 isl_dim_free(dim);
75 return NULL;
76 }
77
78 int isl_qpolynomial_fold_involves_dims(__isl_keep isl_qpolynomial_fold *fold,
79 enum isl_dim_type type, unsigned first, unsigned n)
80 {
81 int i;
82
83 if (!fold)
84 return -1;
85 if (fold->n == 0 || n == 0)
86 return 0;
87
88 for (i = 0; i < fold->n; ++i) {
89 int involves = isl_qpolynomial_involves_dims(fold->qp[i],
90 type, first, n);
91 if (involves < 0 || involves)
92 return involves;
93 }
94 return 0;
95 }
96
97 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_set_dim_name(
98 __isl_take isl_qpolynomial_fold *fold,
99 enum isl_dim_type type, unsigned pos, const char *s)
100 {
101 int i;
102
103 fold = isl_qpolynomial_fold_cow(fold);
104 if (!fold)
105 return NULL;
106 fold->dim = isl_dim_set_name(fold->dim, type, pos, s);
107 if (!fold->dim)
108 goto error;
109
110 for (i = 0; i < fold->n; ++i) {
111 fold->qp[i] = isl_qpolynomial_set_dim_name(fold->qp[i],
112 type, pos, s);
113 if (!fold->qp[i])
114 goto error;
115 }
116
117 return fold;
118 error:
119 isl_qpolynomial_fold_free(fold);
120 return NULL;
121 }
122
123 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_drop_dims(
124 __isl_take isl_qpolynomial_fold *fold,
125 enum isl_dim_type type, unsigned first, unsigned n)
126 {
127 int i;
128
129 if (!fold)
130 return NULL;
131 if (n == 0)
132 return fold;
133
134 fold = isl_qpolynomial_fold_cow(fold);
135 if (!fold)
136 return NULL;
137 fold->dim = isl_dim_drop(fold->dim, type, first, n);
138 if (!fold->dim)
139 goto error;
140
141 for (i = 0; i < fold->n; ++i) {
142 fold->qp[i] = isl_qpolynomial_drop_dims(fold->qp[i],
143 type, first, n);
144 if (!fold->qp[i])
145 goto error;
146 }
147
148 return fold;
149 error:
150 isl_qpolynomial_fold_free(fold);
151 return NULL;
152 }
153
154 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_insert_dims(
155 __isl_take isl_qpolynomial_fold *fold,
156 enum isl_dim_type type, unsigned first, unsigned n)
157 {
158 int i;
159
160 if (!fold)
161 return NULL;
162 if (n == 0 && !isl_dim_is_named_or_nested(fold->dim, type))
163 return fold;
164
165 fold = isl_qpolynomial_fold_cow(fold);
166 if (!fold)
167 return NULL;
168 fold->dim = isl_dim_insert(fold->dim, type, first, n);
169 if (!fold->dim)
170 goto error;
171
172 for (i = 0; i < fold->n; ++i) {
173 fold->qp[i] = isl_qpolynomial_insert_dims(fold->qp[i],
174 type, first, n);
175 if (!fold->qp[i])
176 goto error;
177 }
178
179 return fold;
180 error:
181 isl_qpolynomial_fold_free(fold);
182 return NULL;
183 }
184
185 static int isl_qpolynomial_cst_sign(__isl_keep isl_qpolynomial *qp)
186 {
187 struct isl_upoly_cst *cst;
188
189 cst = isl_upoly_as_cst(qp->upoly);
190 if (!cst)
191 return 0;
192
193 return isl_int_sgn(cst->n) < 0 ? -1 : 1;
194 }
195
196 static int isl_qpolynomial_aff_sign(__isl_keep isl_set *set,
197 __isl_keep isl_qpolynomial *qp)
198 {
199 enum isl_lp_result res;
200 isl_vec *aff;
201 isl_int opt;
202 int sgn = 0;
203
204 aff = isl_qpolynomial_extract_affine(qp);
205 if (!aff)
206 return 0;
207
208 isl_int_init(opt);
209
210 res = isl_set_solve_lp(set, 0, aff->el + 1, aff->el[0],
211 &opt, NULL, NULL);
212 if (res == isl_lp_error)
213 goto done;
214 if (res == isl_lp_empty ||
215 (res == isl_lp_ok && !isl_int_is_neg(opt))) {
216 sgn = 1;
217 goto done;
218 }
219
220 res = isl_set_solve_lp(set, 1, aff->el + 1, aff->el[0],
221 &opt, NULL, NULL);
222 if (res == isl_lp_ok && !isl_int_is_pos(opt))
223 sgn = -1;
224
225 done:
226 isl_int_clear(opt);
227 isl_vec_free(aff);
228 return sgn;
229 }
230
231 /* Determine, if possible, the sign of the quasipolynomial "qp" on
232 * the domain "set".
233 *
234 * If qp is a constant, then the problem is trivial.
235 * If qp is linear, then we check if the minimum of the corresponding
236 * affine constraint is non-negative or if the maximum is non-positive.
237 *
238 * Otherwise, we check if the outermost variable "v" has a lower bound "l"
239 * in "set". If so, we write qp(v,v') as
240 *
241 * q(v,v') * (v - l) + r(v')
242 *
243 * if q(v,v') and r(v') have the same known sign, then the original
244 * quasipolynomial has the same sign as well.
245 *
246 * Return
247 * -1 if qp <= 0
248 * 1 if qp >= 0
249 * 0 if unknown
250 */
251 static int isl_qpolynomial_sign(__isl_keep isl_set *set,
252 __isl_keep isl_qpolynomial *qp)
253 {
254 int d;
255 int i;
256 int is;
257 struct isl_upoly_rec *rec;
258 isl_vec *v;
259 isl_int l;
260 enum isl_lp_result res;
261 int sgn = 0;
262
263 is = isl_qpolynomial_is_cst(qp, NULL, NULL);
264 if (is < 0)
265 return 0;
266 if (is)
267 return isl_qpolynomial_cst_sign(qp);
268
269 is = isl_qpolynomial_is_affine(qp);
270 if (is < 0)
271 return 0;
272 if (is)
273 return isl_qpolynomial_aff_sign(set, qp);
274
275 if (qp->div->n_row > 0)
276 return 0;
277
278 rec = isl_upoly_as_rec(qp->upoly);
279 if (!rec)
280 return 0;
281
282 d = isl_dim_total(qp->dim);
283 v = isl_vec_alloc(set->ctx, 2 + d);
284 if (!v)
285 return 0;
286
287 isl_seq_clr(v->el + 1, 1 + d);
288 isl_int_set_si(v->el[0], 1);
289 isl_int_set_si(v->el[2 + qp->upoly->var], 1);
290
291 isl_int_init(l);
292
293 res = isl_set_solve_lp(set, 0, v->el + 1, v->el[0], &l, NULL, NULL);
294 if (res == isl_lp_ok) {
295 isl_qpolynomial *min;
296 isl_qpolynomial *base;
297 isl_qpolynomial *r, *q;
298 isl_qpolynomial *t;
299
300 min = isl_qpolynomial_cst(isl_dim_copy(qp->dim), l);
301 base = isl_qpolynomial_var_pow(isl_dim_copy(qp->dim),
302 qp->upoly->var, 1);
303
304 r = isl_qpolynomial_alloc(isl_dim_copy(qp->dim), 0,
305 isl_upoly_copy(rec->p[rec->n - 1]));
306 q = isl_qpolynomial_copy(r);
307
308 for (i = rec->n - 2; i >= 0; --i) {
309 r = isl_qpolynomial_mul(r, isl_qpolynomial_copy(min));
310 t = isl_qpolynomial_alloc(isl_dim_copy(qp->dim), 0,
311 isl_upoly_copy(rec->p[i]));
312 r = isl_qpolynomial_add(r, t);
313 if (i == 0)
314 break;
315 q = isl_qpolynomial_mul(q, isl_qpolynomial_copy(base));
316 q = isl_qpolynomial_add(q, isl_qpolynomial_copy(r));
317 }
318
319 if (isl_qpolynomial_is_zero(q))
320 sgn = isl_qpolynomial_sign(set, r);
321 else if (isl_qpolynomial_is_zero(r))
322 sgn = isl_qpolynomial_sign(set, q);
323 else {
324 int sgn_q, sgn_r;
325 sgn_r = isl_qpolynomial_sign(set, r);
326 sgn_q = isl_qpolynomial_sign(set, q);
327 if (sgn_r == sgn_q)
328 sgn = sgn_r;
329 }
330
331 isl_qpolynomial_free(min);
332 isl_qpolynomial_free(base);
333 isl_qpolynomial_free(q);
334 isl_qpolynomial_free(r);
335 }
336
337 isl_int_clear(l);
338
339 isl_vec_free(v);
340
341 return sgn;
342 }
343
344 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold_on_domain(
345 __isl_keep isl_set *set,
346 __isl_take isl_qpolynomial_fold *fold1,
347 __isl_take isl_qpolynomial_fold *fold2)
348 {
349 int i, j;
350 int n1;
351 struct isl_qpolynomial_fold *res = NULL;
352 int better;
353
354 if (!fold1 || !fold2)
355 goto error;
356
357 isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error);
358 isl_assert(fold1->dim->ctx, isl_dim_equal(fold1->dim, fold2->dim),
359 goto error);
360
361 better = fold1->type == isl_fold_max ? -1 : 1;
362
363 if (isl_qpolynomial_fold_is_empty(fold1)) {
364 isl_qpolynomial_fold_free(fold1);
365 return fold2;
366 }
367
368 if (isl_qpolynomial_fold_is_empty(fold2)) {
369 isl_qpolynomial_fold_free(fold2);
370 return fold1;
371 }
372
373 res = qpolynomial_fold_alloc(fold1->type, isl_dim_copy(fold1->dim),
374 fold1->n + fold2->n);
375 if (!res)
376 goto error;
377
378 for (i = 0; i < fold1->n; ++i) {
379 res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]);
380 if (!res->qp[res->n])
381 goto error;
382 res->n++;
383 }
384 n1 = res->n;
385
386 for (i = 0; i < fold2->n; ++i) {
387 for (j = n1 - 1; j >= 0; --j) {
388 isl_qpolynomial *d;
389 int sgn;
390 d = isl_qpolynomial_sub(
391 isl_qpolynomial_copy(res->qp[j]),
392 isl_qpolynomial_copy(fold2->qp[i]));
393 sgn = isl_qpolynomial_sign(set, d);
394 isl_qpolynomial_free(d);
395 if (sgn == 0)
396 continue;
397 if (sgn != better)
398 break;
399 isl_qpolynomial_free(res->qp[j]);
400 if (j != n1 - 1)
401 res->qp[j] = res->qp[n1 - 1];
402 n1--;
403 if (n1 != res->n - 1)
404 res->qp[n1] = res->qp[res->n - 1];
405 res->n--;
406 }
407 if (j >= 0)
408 continue;
409 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
410 if (!res->qp[res->n])
411 goto error;
412 res->n++;
413 }
414
415 isl_qpolynomial_fold_free(fold1);
416 isl_qpolynomial_fold_free(fold2);
417
418 return res;
419 error:
420 isl_qpolynomial_fold_free(res);
421 isl_qpolynomial_fold_free(fold1);
422 isl_qpolynomial_fold_free(fold2);
423 return NULL;
424 }
425
426 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_add_qpolynomial(
427 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_qpolynomial *qp)
428 {
429 int i;
430
431 if (!fold || !qp)
432 goto error;
433
434 if (isl_qpolynomial_is_zero(qp)) {
435 isl_qpolynomial_free(qp);
436 return fold;
437 }
438
439 fold = isl_qpolynomial_fold_cow(fold);
440 if (!fold)
441 goto error;
442
443 for (i = 0; i < fold->n; ++i) {
444 fold->qp[i] = isl_qpolynomial_add(fold->qp[i],
445 isl_qpolynomial_copy(qp));
446 if (!fold->qp[i])
447 goto error;
448 }
449
450 isl_qpolynomial_free(qp);
451 return fold;
452 error:
453 isl_qpolynomial_fold_free(fold);
454 isl_qpolynomial_free(qp);
455 return NULL;
456 }
457
458 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_add_on_domain(
459 __isl_keep isl_set *dom,
460 __isl_take isl_qpolynomial_fold *fold1,
461 __isl_take isl_qpolynomial_fold *fold2)
462 {
463 int i;
464 isl_qpolynomial_fold *res = NULL;
465
466 if (!fold1 || !fold2)
467 goto error;
468
469 if (isl_qpolynomial_fold_is_empty(fold1)) {
470 isl_qpolynomial_fold_free(fold1);
471 return fold2;
472 }
473
474 if (isl_qpolynomial_fold_is_empty(fold2)) {
475 isl_qpolynomial_fold_free(fold2);
476 return fold1;
477 }
478
479 if (fold1->n == 1 && fold2->n != 1)
480 return isl_qpolynomial_fold_add_on_domain(dom, fold2, fold1);
481
482 if (fold2->n == 1) {
483 res = isl_qpolynomial_fold_add_qpolynomial(fold1,
484 isl_qpolynomial_copy(fold2->qp[0]));
485 isl_qpolynomial_fold_free(fold2);
486 return res;
487 }
488
489 res = isl_qpolynomial_fold_add_qpolynomial(
490 isl_qpolynomial_fold_copy(fold1),
491 isl_qpolynomial_copy(fold2->qp[0]));
492
493 for (i = 1; i < fold2->n; ++i) {
494 isl_qpolynomial_fold *res_i;
495 res_i = isl_qpolynomial_fold_add_qpolynomial(
496 isl_qpolynomial_fold_copy(fold1),
497 isl_qpolynomial_copy(fold2->qp[i]));
498 res = isl_qpolynomial_fold_fold_on_domain(dom, res, res_i);
499 }
500
501 isl_qpolynomial_fold_free(fold1);
502 isl_qpolynomial_fold_free(fold2);
503 return res;
504 error:
505 isl_qpolynomial_fold_free(res);
506 isl_qpolynomial_fold_free(fold1);
507 isl_qpolynomial_fold_free(fold2);
508 return NULL;
509 }
510
511 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute_equalities(
512 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_basic_set *eq)
513 {
514 int i;
515
516 if (!fold || !eq)
517 goto error;
518
519 fold = isl_qpolynomial_fold_cow(fold);
520 if (!fold)
521 return NULL;
522
523 for (i = 0; i < fold->n; ++i) {
524 fold->qp[i] = isl_qpolynomial_substitute_equalities(fold->qp[i],
525 isl_basic_set_copy(eq));
526 if (!fold->qp[i])
527 goto error;
528 }
529
530 isl_basic_set_free(eq);
531 return fold;
532 error:
533 isl_basic_set_free(eq);
534 isl_qpolynomial_fold_free(fold);
535 return NULL;
536 }
537
538 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_gist(
539 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *context)
540 {
541 int i;
542
543 if (!fold || !context)
544 goto error;
545
546 fold = isl_qpolynomial_fold_cow(fold);
547 if (!fold)
548 return NULL;
549
550 for (i = 0; i < fold->n; ++i) {
551 fold->qp[i] = isl_qpolynomial_gist(fold->qp[i],
552 isl_set_copy(context));
553 if (!fold->qp[i])
554 goto error;
555 }
556
557 isl_set_free(context);
558 return fold;
559 error:
560 isl_set_free(context);
561 isl_qpolynomial_fold_free(fold);
562 return NULL;
563 }
564
565 #define HAS_TYPE
566
567 #undef PW
568 #define PW isl_pw_qpolynomial_fold
569 #undef EL
570 #define EL isl_qpolynomial_fold
571 #undef IS_ZERO
572 #define IS_ZERO is_empty
573 #undef FIELD
574 #define FIELD fold
575
576 #include <isl_pw_templ.c>
577
578 #undef UNION
579 #define UNION isl_union_pw_qpolynomial_fold
580 #undef PART
581 #define PART isl_pw_qpolynomial_fold
582 #undef PARTS
583 #define PARTS pw_qpolynomial_fold
584
585 #include <isl_union_templ.c>
586
587 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_empty(enum isl_fold type,
588 __isl_take isl_dim *dim)
589 {
590 return qpolynomial_fold_alloc(type, dim, 0);
591 }
592
593 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_alloc(
594 enum isl_fold type, __isl_take isl_qpolynomial *qp)
595 {
596 isl_qpolynomial_fold *fold;
597
598 if (!qp)
599 return NULL;
600
601 fold = qpolynomial_fold_alloc(type, isl_dim_copy(qp->dim), 1);
602 if (!fold)
603 goto error;
604
605 fold->qp[0] = qp;
606 fold->n++;
607
608 return fold;
609 error:
610 isl_qpolynomial_fold_free(fold);
611 isl_qpolynomial_free(qp);
612 return NULL;
613 }
614
615 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_copy(
616 __isl_keep isl_qpolynomial_fold *fold)
617 {
618 if (!fold)
619 return NULL;
620
621 fold->ref++;
622 return fold;
623 }
624
625 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_dup(
626 __isl_keep isl_qpolynomial_fold *fold)
627 {
628 int i;
629 isl_qpolynomial_fold *dup;
630
631 if (!fold)
632 return NULL;
633 dup = qpolynomial_fold_alloc(fold->type,
634 isl_dim_copy(fold->dim), fold->n);
635 if (!dup)
636 return NULL;
637
638 dup->n = fold->n;
639 for (i = 0; i < fold->n; ++i) {
640 dup->qp[i] = isl_qpolynomial_copy(fold->qp[i]);
641 if (!dup->qp[i])
642 goto error;
643 }
644
645 return dup;
646 error:
647 isl_qpolynomial_fold_free(dup);
648 return NULL;
649 }
650
651 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_cow(
652 __isl_take isl_qpolynomial_fold *fold)
653 {
654 if (!fold)
655 return NULL;
656
657 if (fold->ref == 1)
658 return fold;
659 fold->ref--;
660 return isl_qpolynomial_fold_dup(fold);
661 }
662
663 void isl_qpolynomial_fold_free(__isl_take isl_qpolynomial_fold *fold)
664 {
665 int i;
666
667 if (!fold)
668 return;
669 if (--fold->ref > 0)
670 return;
671
672 for (i = 0; i < fold->n; ++i)
673 isl_qpolynomial_free(fold->qp[i]);
674 isl_dim_free(fold->dim);
675 free(fold);
676 }
677
678 int isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold *fold)
679 {
680 if (!fold)
681 return -1;
682
683 return fold->n == 0;
684 }
685
686 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold(
687 __isl_take isl_qpolynomial_fold *fold1,
688 __isl_take isl_qpolynomial_fold *fold2)
689 {
690 int i;
691 struct isl_qpolynomial_fold *res = NULL;
692
693 if (!fold1 || !fold2)
694 goto error;
695
696 isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error);
697 isl_assert(fold1->dim->ctx, isl_dim_equal(fold1->dim, fold2->dim),
698 goto error);
699
700 if (isl_qpolynomial_fold_is_empty(fold1)) {
701 isl_qpolynomial_fold_free(fold1);
702 return fold2;
703 }
704
705 if (isl_qpolynomial_fold_is_empty(fold2)) {
706 isl_qpolynomial_fold_free(fold2);
707 return fold1;
708 }
709
710 res = qpolynomial_fold_alloc(fold1->type, isl_dim_copy(fold1->dim),
711 fold1->n + fold2->n);
712 if (!res)
713 goto error;
714
715 for (i = 0; i < fold1->n; ++i) {
716 res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]);
717 if (!res->qp[res->n])
718 goto error;
719 res->n++;
720 }
721
722 for (i = 0; i < fold2->n; ++i) {
723 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
724 if (!res->qp[res->n])
725 goto error;
726 res->n++;
727 }
728
729 isl_qpolynomial_fold_free(fold1);
730 isl_qpolynomial_fold_free(fold2);
731
732 return res;
733 error:
734 isl_qpolynomial_fold_free(res);
735 isl_qpolynomial_fold_free(fold1);
736 isl_qpolynomial_fold_free(fold2);
737 return NULL;
738 }
739
740 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_fold(
741 __isl_take isl_pw_qpolynomial_fold *pw1,
742 __isl_take isl_pw_qpolynomial_fold *pw2)
743 {
744 int i, j, n;
745 struct isl_pw_qpolynomial_fold *res;
746 isl_set *set;
747
748 if (!pw1 || !pw2)
749 goto error;
750
751 isl_assert(pw1->dim->ctx, isl_dim_equal(pw1->dim, pw2->dim), goto error);
752
753 if (isl_pw_qpolynomial_fold_is_zero(pw1)) {
754 isl_pw_qpolynomial_fold_free(pw1);
755 return pw2;
756 }
757
758 if (isl_pw_qpolynomial_fold_is_zero(pw2)) {
759 isl_pw_qpolynomial_fold_free(pw2);
760 return pw1;
761 }
762
763 if (pw1->type != pw2->type)
764 isl_die(set->ctx, isl_error_invalid, "fold types don't match",
765 goto error);
766
767 n = (pw1->n + 1) * (pw2->n + 1);
768 res = isl_pw_qpolynomial_fold_alloc_(isl_dim_copy(pw1->dim),
769 pw1->type, n);
770
771 for (i = 0; i < pw1->n; ++i) {
772 set = isl_set_copy(pw1->p[i].set);
773 for (j = 0; j < pw2->n; ++j) {
774 struct isl_set *common;
775 isl_qpolynomial_fold *sum;
776 set = isl_set_subtract(set,
777 isl_set_copy(pw2->p[j].set));
778 common = isl_set_intersect(isl_set_copy(pw1->p[i].set),
779 isl_set_copy(pw2->p[j].set));
780 if (isl_set_fast_is_empty(common)) {
781 isl_set_free(common);
782 continue;
783 }
784
785 sum = isl_qpolynomial_fold_fold_on_domain(common,
786 isl_qpolynomial_fold_copy(pw1->p[i].fold),
787 isl_qpolynomial_fold_copy(pw2->p[j].fold));
788
789 res = isl_pw_qpolynomial_fold_add_piece(res, common, sum);
790 }
791 res = isl_pw_qpolynomial_fold_add_piece(res, set,
792 isl_qpolynomial_fold_copy(pw1->p[i].fold));
793 }
794
795 for (j = 0; j < pw2->n; ++j) {
796 set = isl_set_copy(pw2->p[j].set);
797 for (i = 0; i < pw1->n; ++i)
798 set = isl_set_subtract(set, isl_set_copy(pw1->p[i].set));
799 res = isl_pw_qpolynomial_fold_add_piece(res, set,
800 isl_qpolynomial_fold_copy(pw2->p[j].fold));
801 }
802
803 isl_pw_qpolynomial_fold_free(pw1);
804 isl_pw_qpolynomial_fold_free(pw2);
805
806 return res;
807 error:
808 isl_pw_qpolynomial_fold_free(pw1);
809 isl_pw_qpolynomial_fold_free(pw2);
810 return NULL;
811 }
812
813 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
814 __isl_take isl_union_pw_qpolynomial_fold *u,
815 __isl_take isl_pw_qpolynomial_fold *part)
816 {
817 uint32_t hash;
818 struct isl_hash_table_entry *entry;
819
820 u = isl_union_pw_qpolynomial_fold_cow(u);
821
822 if (!part || !u)
823 goto error;
824
825 isl_assert(u->dim->ctx, isl_dim_match(part->dim, isl_dim_param, u->dim,
826 isl_dim_param), goto error);
827
828 hash = isl_dim_get_hash(part->dim);
829 entry = isl_hash_table_find(u->dim->ctx, &u->table, hash,
830 &has_dim, part->dim, 1);
831 if (!entry)
832 goto error;
833
834 if (!entry->data)
835 entry->data = part;
836 else {
837 entry->data = isl_pw_qpolynomial_fold_fold(entry->data,
838 isl_pw_qpolynomial_fold_copy(part));
839 if (!entry->data)
840 goto error;
841 isl_pw_qpolynomial_fold_free(part);
842 }
843
844 return u;
845 error:
846 isl_pw_qpolynomial_fold_free(part);
847 isl_union_pw_qpolynomial_fold_free(u);
848 return NULL;
849 }
850
851 static int fold_part(__isl_take isl_pw_qpolynomial_fold *part, void *user)
852 {
853 isl_union_pw_qpolynomial_fold **u;
854 u = (isl_union_pw_qpolynomial_fold **)user;
855
856 *u = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(*u, part);
857
858 return 0;
859 }
860
861 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold(
862 __isl_take isl_union_pw_qpolynomial_fold *u1,
863 __isl_take isl_union_pw_qpolynomial_fold *u2)
864 {
865 u1 = isl_union_pw_qpolynomial_fold_cow(u1);
866
867 if (!u1 || !u2)
868 goto error;
869
870 if (isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(u2,
871 &fold_part, &u1) < 0)
872 goto error;
873
874 isl_union_pw_qpolynomial_fold_free(u2);
875
876 return u1;
877 error:
878 isl_union_pw_qpolynomial_fold_free(u1);
879 isl_union_pw_qpolynomial_fold_free(u2);
880 return NULL;
881 }
882
883 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_from_pw_qpolynomial(
884 enum isl_fold type, __isl_take isl_pw_qpolynomial *pwqp)
885 {
886 int i;
887 isl_pw_qpolynomial_fold *pwf;
888
889 if (!pwqp)
890 return NULL;
891
892 pwf = isl_pw_qpolynomial_fold_alloc_(isl_dim_copy(pwqp->dim), type,
893 pwqp->n);
894
895 for (i = 0; i < pwqp->n; ++i)
896 pwf = isl_pw_qpolynomial_fold_add_piece(pwf,
897 isl_set_copy(pwqp->p[i].set),
898 isl_qpolynomial_fold_alloc(type,
899 isl_qpolynomial_copy(pwqp->p[i].qp)));
900
901 isl_pw_qpolynomial_free(pwqp);
902
903 return pwf;
904 }
905
906 int isl_qpolynomial_fold_is_equal(__isl_keep isl_qpolynomial_fold *fold1,
907 __isl_keep isl_qpolynomial_fold *fold2)
908 {
909 int i;
910
911 if (!fold1 || !fold2)
912 return -1;
913
914 if (fold1->n != fold2->n)
915 return 0;
916
917 /* We probably want to sort the qps first... */
918 for (i = 0; i < fold1->n; ++i) {
919 int eq = isl_qpolynomial_is_equal(fold1->qp[i], fold2->qp[i]);
920 if (eq < 0 || !eq)
921 return eq;
922 }
923
924 return 1;
925 }
926
927 __isl_give isl_qpolynomial *isl_qpolynomial_fold_eval(
928 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_point *pnt)
929 {
930 isl_qpolynomial *qp;
931
932 if (!fold || !pnt)
933 goto error;
934 isl_assert(pnt->dim->ctx, isl_dim_equal(pnt->dim, fold->dim), goto error);
935 isl_assert(pnt->dim->ctx,
936 fold->type == isl_fold_max || fold->type == isl_fold_min,
937 goto error);
938
939 if (fold->n == 0)
940 qp = isl_qpolynomial_zero(isl_dim_copy(fold->dim));
941 else {
942 int i;
943 qp = isl_qpolynomial_eval(isl_qpolynomial_copy(fold->qp[0]),
944 isl_point_copy(pnt));
945 for (i = 1; i < fold->n; ++i) {
946 isl_qpolynomial *qp_i;
947 qp_i = isl_qpolynomial_eval(
948 isl_qpolynomial_copy(fold->qp[i]),
949 isl_point_copy(pnt));
950 if (fold->type == isl_fold_max)
951 qp = isl_qpolynomial_max_cst(qp, qp_i);
952 else
953 qp = isl_qpolynomial_min_cst(qp, qp_i);
954 }
955 }
956 isl_qpolynomial_fold_free(fold);
957 isl_point_free(pnt);
958
959 return qp;
960 error:
961 isl_qpolynomial_fold_free(fold);
962 isl_point_free(pnt);
963 return NULL;
964 }
965
966 size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold *pwf)
967 {
968 int i;
969 size_t n = 0;
970
971 for (i = 0; i < pwf->n; ++i)
972 n += pwf->p[i].fold->n;
973
974 return n;
975 }
976
977 __isl_give isl_qpolynomial *isl_qpolynomial_fold_opt_on_domain(
978 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *set, int max)
979 {
980 int i;
981 isl_qpolynomial *opt;
982
983 if (!set || !fold)
984 goto error;
985
986 if (fold->n == 0) {
987 isl_dim *dim = isl_dim_copy(fold->dim);
988 isl_set_free(set);
989 isl_qpolynomial_fold_free(fold);
990 return isl_qpolynomial_zero(dim);
991 }
992
993 opt = isl_qpolynomial_opt_on_domain(isl_qpolynomial_copy(fold->qp[0]),
994 isl_set_copy(set), max);
995 for (i = 1; i < fold->n; ++i) {
996 isl_qpolynomial *opt_i;
997 opt_i = isl_qpolynomial_opt_on_domain(
998 isl_qpolynomial_copy(fold->qp[i]),
999 isl_set_copy(set), max);
1000 if (max)
1001 opt = isl_qpolynomial_max_cst(opt, opt_i);
1002 else
1003 opt = isl_qpolynomial_min_cst(opt, opt_i);
1004 }
1005
1006 isl_set_free(set);
1007 isl_qpolynomial_fold_free(fold);
1008
1009 return opt;
1010 error:
1011 isl_set_free(set);
1012 isl_qpolynomial_fold_free(fold);
1013 return NULL;
1014 }
1015
1016 /* Check whether for each quasi-polynomial in "fold2" there is
1017 * a quasi-polynomial in "fold1" that dominates it on "set".
1018 */
1019 static int qpolynomial_fold_covers_on_domain(__isl_keep isl_set *set,
1020 __isl_keep isl_qpolynomial_fold *fold1,
1021 __isl_keep isl_qpolynomial_fold *fold2)
1022 {
1023 int i, j;
1024 int covers;
1025
1026 if (!set || !fold1 || !fold2)
1027 return -1;
1028
1029 covers = fold1->type == isl_fold_max ? 1 : -1;
1030
1031 for (i = 0; i < fold2->n; ++i) {
1032 for (j = 0; j < fold1->n; ++j) {
1033 isl_qpolynomial *d;
1034 int sgn;
1035
1036 d = isl_qpolynomial_sub(
1037 isl_qpolynomial_copy(fold1->qp[j]),
1038 isl_qpolynomial_copy(fold2->qp[i]));
1039 sgn = isl_qpolynomial_sign(set, d);
1040 isl_qpolynomial_free(d);
1041 if (sgn == covers)
1042 break;
1043 }
1044 if (j >= fold1->n)
1045 return 0;
1046 }
1047
1048 return 1;
1049 }
1050
1051 /* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains
1052 * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates
1053 * that of pwf2.
1054 */
1055 int isl_pw_qpolynomial_fold_covers(__isl_keep isl_pw_qpolynomial_fold *pwf1,
1056 __isl_keep isl_pw_qpolynomial_fold *pwf2)
1057 {
1058 int i, j;
1059 isl_set *dom1, *dom2;
1060 int is_subset;
1061
1062 if (!pwf1 || !pwf2)
1063 return -1;
1064
1065 if (pwf2->n == 0)
1066 return 1;
1067 if (pwf1->n == 0)
1068 return 0;
1069
1070 dom1 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1));
1071 dom2 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2));
1072 is_subset = isl_set_is_subset(dom2, dom1);
1073 isl_set_free(dom1);
1074 isl_set_free(dom2);
1075
1076 if (is_subset < 0 || !is_subset)
1077 return is_subset;
1078
1079 for (i = 0; i < pwf2->n; ++i) {
1080 for (j = 0; j < pwf1->n; ++j) {
1081 int is_empty;
1082 isl_set *common;
1083 int covers;
1084
1085 common = isl_set_intersect(isl_set_copy(pwf1->p[j].set),
1086 isl_set_copy(pwf2->p[i].set));
1087 is_empty = isl_set_is_empty(common);
1088 if (is_empty < 0 || is_empty) {
1089 isl_set_free(common);
1090 if (is_empty < 0)
1091 return -1;
1092 continue;
1093 }
1094 covers = qpolynomial_fold_covers_on_domain(common,
1095 pwf1->p[j].fold, pwf2->p[i].fold);
1096 isl_set_free(common);
1097 if (covers < 0 || !covers)
1098 return covers;
1099 }
1100 }
1101
1102 return 1;
1103 }
1104
1105 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_morph(
1106 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_morph *morph)
1107 {
1108 int i;
1109 isl_ctx *ctx;
1110
1111 if (!fold || !morph)
1112 goto error;
1113
1114 ctx = fold->dim->ctx;
1115 isl_assert(ctx, isl_dim_equal(fold->dim, morph->dom->dim), goto error);
1116
1117 fold = isl_qpolynomial_fold_cow(fold);
1118 if (!fold)
1119 goto error;
1120
1121 isl_dim_free(fold->dim);
1122 fold->dim = isl_dim_copy(morph->ran->dim);
1123 if (!fold->dim)
1124 goto error;
1125
1126 for (i = 0; i < fold->n; ++i) {
1127 fold->qp[i] = isl_qpolynomial_morph(fold->qp[i],
1128 isl_morph_copy(morph));
1129 if (!fold->qp[i])
1130 goto error;
1131 }
1132
1133 isl_morph_free(morph);
1134
1135 return fold;
1136 error:
1137 isl_qpolynomial_fold_free(fold);
1138 isl_morph_free(morph);
1139 return NULL;
1140 }
1141
1142 enum isl_fold isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold *fold)
1143 {
1144 if (!fold)
1145 return isl_fold_list;
1146 return fold->type;
1147 }
1148
1149 enum isl_fold isl_union_pw_qpolynomial_fold_get_type(
1150 __isl_keep isl_union_pw_qpolynomial_fold *upwf)
1151 {
1152 if (!upwf)
1153 return isl_fold_list;
1154 return upwf->type;
1155 }
1156
1157 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_lift(
1158 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_dim *dim)
1159 {
1160 int i;
1161 isl_ctx *ctx;
1162
1163 if (!fold || !dim)
1164 goto error;
1165
1166 if (isl_dim_equal(fold->dim, dim)) {
1167 isl_dim_free(dim);
1168 return fold;
1169 }
1170
1171 fold = isl_qpolynomial_fold_cow(fold);
1172 if (!fold)
1173 goto error;
1174
1175 isl_dim_free(fold->dim);
1176 fold->dim = isl_dim_copy(dim);
1177 if (!fold->dim)
1178 goto error;
1179
1180 for (i = 0; i < fold->n; ++i) {
1181 fold->qp[i] = isl_qpolynomial_lift(fold->qp[i],
1182 isl_dim_copy(dim));
1183 if (!fold->qp[i])
1184 goto error;
1185 }
1186
1187 isl_dim_free(dim);
1188
1189 return fold;
1190 error:
1191 isl_qpolynomial_fold_free(fold);
1192 isl_dim_free(dim);
1193 return NULL;
1194 }
1195
1196 int isl_qpolynomial_fold_foreach_qpolynomial(
1197 __isl_keep isl_qpolynomial_fold *fold,
1198 int (*fn)(__isl_take isl_qpolynomial *qp, void *user), void *user)
1199 {
1200 int i;
1201
1202 if (!fold)
1203 return -1;
1204
1205 for (i = 0; i < fold->n; ++i)
1206 if (fn(isl_qpolynomial_copy(fold->qp[i]), user) < 0)
1207 return -1;
1208
1209 return 0;
1210 }
1211
1212 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_move_dims(
1213 __isl_take isl_qpolynomial_fold *fold,
1214 enum isl_dim_type dst_type, unsigned dst_pos,
1215 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1216 {
1217 int i;
1218
1219 if (n == 0)
1220 return fold;
1221
1222 fold = isl_qpolynomial_fold_cow(fold);
1223 if (!fold)
1224 return NULL;
1225
1226 fold->dim = isl_dim_move(fold->dim, dst_type, dst_pos,
1227 src_type, src_pos, n);
1228 if (!fold->dim)
1229 goto error;
1230
1231 for (i = 0; i < fold->n; ++i) {
1232 fold->qp[i] = isl_qpolynomial_move_dims(fold->qp[i],
1233 dst_type, dst_pos, src_type, src_pos, n);
1234 if (!fold->qp[i])
1235 goto error;
1236 }
1237
1238 return fold;
1239 error:
1240 isl_qpolynomial_fold_free(fold);
1241 return NULL;
1242 }
1243
1244 /* For each 0 <= i < "n", replace variable "first" + i of type "type"
1245 * in fold->qp[k] by subs[i].
1246 */
1247 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute(
1248 __isl_take isl_qpolynomial_fold *fold,
1249 enum isl_dim_type type, unsigned first, unsigned n,
1250 __isl_keep isl_qpolynomial **subs)
1251 {
1252 int i;
1253
1254 if (n == 0)
1255 return fold;
1256
1257 fold = isl_qpolynomial_fold_cow(fold);
1258 if (!fold)
1259 return NULL;
1260
1261 for (i = 0; i < fold->n; ++i) {
1262 fold->qp[i] = isl_qpolynomial_substitute(fold->qp[i],
1263 type, first, n, subs);
1264 if (!fold->qp[i])
1265 goto error;
1266 }
1267
1268 return fold;
1269 error:
1270 isl_qpolynomial_fold_free(fold);
1271 return NULL;
1272 }
1273
1274 static int add_pwqp(__isl_take isl_pw_qpolynomial *pwqp, void *user)
1275 {
1276 isl_ctx *ctx;
1277 isl_pw_qpolynomial_fold *pwf;
1278 isl_union_pw_qpolynomial_fold **upwf;
1279 uint32_t hash;
1280 struct isl_hash_table_entry *entry;
1281
1282 upwf = (isl_union_pw_qpolynomial_fold **)user;
1283
1284 ctx = pwqp->dim->ctx;
1285 hash = isl_dim_get_hash(pwqp->dim);
1286 entry = isl_hash_table_find(ctx, &(*upwf)->table,
1287 hash, &has_dim, pwqp->dim, 1);
1288 if (!entry)
1289 goto error;
1290
1291 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial((*upwf)->type, pwqp);
1292 if (!entry->data)
1293 entry->data = pwf;
1294 else {
1295 entry->data = isl_pw_qpolynomial_fold_add(entry->data, pwf);
1296 if (!entry->data)
1297 return -1;
1298 if (isl_pw_qpolynomial_fold_is_zero(entry->data)) {
1299 isl_pw_qpolynomial_fold_free(entry->data);
1300 isl_hash_table_remove(ctx, &(*upwf)->table, entry);
1301 }
1302 }
1303
1304 return 0;
1305 error:
1306 isl_pw_qpolynomial_free(pwqp);
1307 return -1;
1308 }
1309
1310 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial(
1311 __isl_take isl_union_pw_qpolynomial_fold *upwf,
1312 __isl_take isl_union_pw_qpolynomial *upwqp)
1313 {
1314 upwf = isl_union_pw_qpolynomial_fold_align_params(upwf,
1315 isl_union_pw_qpolynomial_get_dim(upwqp));
1316 upwqp = isl_union_pw_qpolynomial_align_params(upwqp,
1317 isl_union_pw_qpolynomial_fold_get_dim(upwf));
1318
1319 upwf = isl_union_pw_qpolynomial_fold_cow(upwf);
1320 if (!upwf || !upwqp)
1321 goto error;
1322
1323 if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp, &add_pwqp,
1324 &upwf) < 0)
1325 goto error;
1326
1327 isl_union_pw_qpolynomial_free(upwqp);
1328
1329 return upwf;
1330 error:
1331 isl_union_pw_qpolynomial_fold_free(upwf);
1332 isl_union_pw_qpolynomial_free(upwqp);
1333 return NULL;
1334 }
1335
1336 static int compatible_range(__isl_keep isl_dim *dim1, __isl_keep isl_dim *dim2)
1337 {
1338 int m;
1339 m = isl_dim_match(dim1, isl_dim_param, dim2, isl_dim_param);
1340 if (m < 0 || !m)
1341 return m;
1342 return isl_dim_tuple_match(dim1, isl_dim_out, dim2, isl_dim_set);
1343 }
1344
1345 /* Compute the intersection of the range of the map and the domain
1346 * of the piecewise quasipolynomial reduction and then compute a bound
1347 * on the associated quasipolynomial reduction over all elements
1348 * in this intersection.
1349 *
1350 * We first introduce some unconstrained dimensions in the
1351 * piecewise quasipolynomial, intersect the resulting domain
1352 * with the wrapped map and the compute the sum.
1353 */
1354 __isl_give isl_pw_qpolynomial_fold *isl_map_apply_pw_qpolynomial_fold(
1355 __isl_take isl_map *map, __isl_take isl_pw_qpolynomial_fold *pwf,
1356 int *tight)
1357 {
1358 isl_ctx *ctx;
1359 isl_set *dom;
1360 isl_dim *map_dim;
1361 isl_dim *pwf_dim;
1362 unsigned n_in;
1363 int ok;
1364
1365 ctx = isl_map_get_ctx(map);
1366 if (!ctx)
1367 goto error;
1368
1369 map_dim = isl_map_get_dim(map);
1370 pwf_dim = isl_pw_qpolynomial_fold_get_dim(pwf);
1371 ok = compatible_range(map_dim, pwf_dim);
1372 isl_dim_free(map_dim);
1373 isl_dim_free(pwf_dim);
1374 if (!ok)
1375 isl_die(ctx, isl_error_invalid, "incompatible dimensions",
1376 goto error);
1377
1378 n_in = isl_map_dim(map, isl_dim_in);
1379 pwf = isl_pw_qpolynomial_fold_insert_dims(pwf, isl_dim_set, 0, n_in);
1380
1381 dom = isl_map_wrap(map);
1382 pwf = isl_pw_qpolynomial_fold_reset_dim(pwf, isl_set_get_dim(dom));
1383
1384 pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, dom);
1385 pwf = isl_pw_qpolynomial_fold_bound(pwf, tight);
1386
1387 return pwf;
1388 error:
1389 isl_map_free(map);
1390 isl_pw_qpolynomial_fold_free(pwf);
1391 return NULL;
1392 }
1393
1394 struct isl_apply_fold_data {
1395 isl_union_pw_qpolynomial_fold *upwf;
1396 isl_union_pw_qpolynomial_fold *res;
1397 isl_map *map;
1398 int tight;
1399 };
1400
1401 static int pw_qpolynomial_fold_apply(__isl_take isl_pw_qpolynomial_fold *pwf,
1402 void *user)
1403 {
1404 isl_dim *map_dim;
1405 isl_dim *pwf_dim;
1406 struct isl_apply_fold_data *data = user;
1407 int ok;
1408
1409 map_dim = isl_map_get_dim(data->map);
1410 pwf_dim = isl_pw_qpolynomial_fold_get_dim(pwf);
1411 ok = compatible_range(map_dim, pwf_dim);
1412 isl_dim_free(map_dim);
1413 isl_dim_free(pwf_dim);
1414
1415 if (ok) {
1416 pwf = isl_map_apply_pw_qpolynomial_fold(isl_map_copy(data->map),
1417 pwf, data->tight ? &data->tight : NULL);
1418 data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
1419 data->res, pwf);
1420 } else
1421 isl_pw_qpolynomial_fold_free(pwf);
1422
1423 return 0;
1424 }
1425
1426 static int map_apply(__isl_take isl_map *map, void *user)
1427 {
1428 struct isl_apply_fold_data *data = user;
1429 int r;
1430
1431 data->map = map;
1432 r = isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(
1433 data->upwf, &pw_qpolynomial_fold_apply, data);
1434
1435 isl_map_free(map);
1436 return r;
1437 }
1438
1439 __isl_give isl_union_pw_qpolynomial_fold *isl_union_map_apply_union_pw_qpolynomial_fold(
1440 __isl_take isl_union_map *umap,
1441 __isl_take isl_union_pw_qpolynomial_fold *upwf, int *tight)
1442 {
1443 isl_dim *dim;
1444 enum isl_fold type;
1445 struct isl_apply_fold_data data;
1446
1447 upwf = isl_union_pw_qpolynomial_fold_align_params(upwf,
1448 isl_union_map_get_dim(umap));
1449 umap = isl_union_map_align_params(umap,
1450 isl_union_pw_qpolynomial_fold_get_dim(upwf));
1451
1452 data.upwf = upwf;
1453 data.tight = tight ? 1 : 0;
1454 dim = isl_union_pw_qpolynomial_fold_get_dim(upwf);
1455 type = isl_union_pw_qpolynomial_fold_get_type(upwf);
1456 data.res = isl_union_pw_qpolynomial_fold_zero(dim, type);
1457 if (isl_union_map_foreach_map(umap, &map_apply, &data) < 0)
1458 goto error;
1459
1460 isl_union_map_free(umap);
1461 isl_union_pw_qpolynomial_fold_free(upwf);
1462
1463 if (tight)
1464 *tight = data.tight;
1465
1466 return data.res;
1467 error:
1468 isl_union_map_free(umap);
1469 isl_union_pw_qpolynomial_fold_free(upwf);
1470 isl_union_pw_qpolynomial_fold_free(data.res);
1471 return NULL;
1472 }
1473
1474 /* Reorder the dimension of "fold" according to the given reordering.
1475 */
1476 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_realign(
1477 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_reordering *r)
1478 {
1479 int i;
1480
1481 fold = isl_qpolynomial_fold_cow(fold);
1482 if (!fold || !r)
1483 goto error;
1484
1485 for (i = 0; i < fold->n; ++i) {
1486 fold->qp[i] = isl_qpolynomial_realign(fold->qp[i],
1487 isl_reordering_copy(r));
1488 if (!fold->qp[i])
1489 goto error;
1490 }
1491
1492 fold = isl_qpolynomial_fold_reset_dim(fold, isl_dim_copy(r->dim));
1493
1494 isl_reordering_free(r);
1495
1496 return fold;
1497 error:
1498 isl_qpolynomial_fold_free(fold);
1499 isl_reordering_free(r);
1500 return NULL;
1501 }
Integer set library