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