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