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