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