?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_stream_read_obj: read reductions
[isl.git] / isl_fold.c
blobfd50f902435fe0c77145a94f9d83e04244b9363c
1 /*
2 * Copyright 2010 INRIA Saclay
3 *
4 * Use of this software is governed by the GNU LGPLv2.1 license
5 *
6 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
8 * 91893 Orsay, France
9 */
10
11 #include <isl_union_map_private.h>
12 #include <isl_polynomial_private.h>
13 #include <isl_point_private.h>
14 #include <isl_dim_private.h>
15 #include <isl_map_private.h>
16 #include <isl_lp.h>
17 #include <isl_seq.h>
18
19 static __isl_give isl_qpolynomial_fold *qpolynomial_fold_alloc(
20 enum isl_fold type, __isl_take isl_dim *dim, int n)
21 {
22 isl_qpolynomial_fold *fold;
23
24 if (!dim)
25 goto error;
26
27 isl_assert(dim->ctx, n >= 0, goto error);
28 fold = isl_calloc(dim->ctx, struct isl_qpolynomial_fold,
29 sizeof(struct isl_qpolynomial_fold) +
30 (n - 1) * sizeof(struct isl_qpolynomial *));
31 if (!fold)
32 goto error;
33
34 fold->ref = 1;
35 fold->size = n;
36 fold->n = 0;
37 fold->type = type;
38 fold->dim = dim;
39
40 return fold;
41 error:
42 isl_dim_free(dim);
43 return NULL;
44 }
45
46 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_reset_dim(
47 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_dim *dim)
48 {
49 if (!fold || !dim)
50 goto error;
51
52 isl_dim_free(fold->dim);
53 fold->dim = dim;
54
55 return fold;
56 error:
57 isl_qpolynomial_fold_free(fold);
58 isl_dim_free(dim);
59 return NULL;
60 }
61
62 int isl_qpolynomial_fold_involves_dims(__isl_keep isl_qpolynomial_fold *fold,
63 enum isl_dim_type type, unsigned first, unsigned n)
64 {
65 int i;
66
67 if (!fold)
68 return -1;
69 if (fold->n == 0 || n == 0)
70 return 0;
71
72 for (i = 0; i < fold->n; ++i) {
73 int involves = isl_qpolynomial_involves_dims(fold->qp[i],
74 type, first, n);
75 if (involves < 0 || involves)
76 return involves;
77 }
78 return 0;
79 }
80
81 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_drop_dims(
82 __isl_take isl_qpolynomial_fold *fold,
83 enum isl_dim_type type, unsigned first, unsigned n)
84 {
85 int i;
86
87 if (!fold)
88 return NULL;
89 if (n == 0)
90 return fold;
91
92 fold = isl_qpolynomial_fold_cow(fold);
93 if (!fold)
94 return NULL;
95 fold->dim = isl_dim_drop(fold->dim, type, first, n);
96 if (!fold->dim)
97 goto error;
98
99 for (i = 0; i < fold->n; ++i) {
100 fold->qp[i] = isl_qpolynomial_drop_dims(fold->qp[i],
101 type, first, n);
102 if (!fold->qp[i])
103 goto error;
104 }
105
106 return fold;
107 error:
108 isl_qpolynomial_fold_free(fold);
109 return NULL;
110 }
111
112 static int isl_qpolynomial_cst_sign(__isl_keep isl_qpolynomial *qp)
113 {
114 struct isl_upoly_cst *cst;
115
116 cst = isl_upoly_as_cst(qp->upoly);
117 if (!cst)
118 return 0;
119
120 return isl_int_sgn(cst->n) < 0 ? -1 : 1;
121 }
122
123 static int isl_qpolynomial_aff_sign(__isl_keep isl_set *set,
124 __isl_keep isl_qpolynomial *qp)
125 {
126 enum isl_lp_result res;
127 isl_vec *aff;
128 isl_int opt;
129 int sgn = 0;
130
131 aff = isl_qpolynomial_extract_affine(qp);
132 if (!aff)
133 return 0;
134
135 isl_int_init(opt);
136
137 res = isl_set_solve_lp(set, 0, aff->el + 1, aff->el[0],
138 &opt, NULL, NULL);
139 if (res == isl_lp_error)
140 goto done;
141 if (res == isl_lp_empty ||
142 (res == isl_lp_ok && !isl_int_is_neg(opt))) {
143 sgn = 1;
144 goto done;
145 }
146
147 res = isl_set_solve_lp(set, 1, aff->el + 1, aff->el[0],
148 &opt, NULL, NULL);
149 if (res == isl_lp_ok && !isl_int_is_pos(opt))
150 sgn = -1;
151
152 done:
153 isl_int_clear(opt);
154 isl_vec_free(aff);
155 return sgn;
156 }
157
158 /* Determine, if possible, the sign of the quasipolynomial "qp" on
159 * the domain "set".
160 *
161 * If qp is a constant, then the problem is trivial.
162 * If qp is linear, then we check if the minimum of the corresponding
163 * affine constraint is non-negative or if the maximum is non-positive.
164 *
165 * Otherwise, we check if the outermost variable "v" has a lower bound "l"
166 * in "set". If so, we write qp(v,v') as
167 *
168 * q(v,v') * (v - l) + r(v')
169 *
170 * if q(v,v') and r(v') have the same known sign, then the original
171 * quasipolynomial has the same sign as well.
172 *
173 * Return
174 * -1 if qp <= 0
175 * 1 if qp >= 0
176 * 0 if unknown
177 */
178 static int isl_qpolynomial_sign(__isl_keep isl_set *set,
179 __isl_keep isl_qpolynomial *qp)
180 {
181 int d;
182 int i;
183 int is;
184 struct isl_upoly_rec *rec;
185 isl_vec *v;
186 isl_int l;
187 enum isl_lp_result res;
188 int sgn = 0;
189
190 is = isl_qpolynomial_is_cst(qp, NULL, NULL);
191 if (is < 0)
192 return 0;
193 if (is)
194 return isl_qpolynomial_cst_sign(qp);
195
196 is = isl_qpolynomial_is_affine(qp);
197 if (is < 0)
198 return 0;
199 if (is)
200 return isl_qpolynomial_aff_sign(set, qp);
201
202 if (qp->div->n_row > 0)
203 return 0;
204
205 rec = isl_upoly_as_rec(qp->upoly);
206 if (!rec)
207 return 0;
208
209 d = isl_dim_total(qp->dim);
210 v = isl_vec_alloc(set->ctx, 2 + d);
211 if (!v)
212 return 0;
213
214 isl_seq_clr(v->el + 1, 1 + d);
215 isl_int_set_si(v->el[0], 1);
216 isl_int_set_si(v->el[2 + qp->upoly->var], 1);
217
218 isl_int_init(l);
219
220 res = isl_set_solve_lp(set, 0, v->el + 1, v->el[0], &l, NULL, NULL);
221 if (res == isl_lp_ok) {
222 isl_qpolynomial *min;
223 isl_qpolynomial *base;
224 isl_qpolynomial *r, *q;
225 isl_qpolynomial *t;
226
227 min = isl_qpolynomial_cst(isl_dim_copy(qp->dim), l);
228 base = isl_qpolynomial_pow(isl_dim_copy(qp->dim),
229 qp->upoly->var, 1);
230
231 r = isl_qpolynomial_alloc(isl_dim_copy(qp->dim), 0,
232 isl_upoly_copy(rec->p[rec->n - 1]));
233 q = isl_qpolynomial_copy(r);
234
235 for (i = rec->n - 2; i >= 0; --i) {
236 r = isl_qpolynomial_mul(r, isl_qpolynomial_copy(min));
237 t = isl_qpolynomial_alloc(isl_dim_copy(qp->dim), 0,
238 isl_upoly_copy(rec->p[i]));
239 r = isl_qpolynomial_add(r, t);
240 if (i == 0)
241 break;
242 q = isl_qpolynomial_mul(q, isl_qpolynomial_copy(base));
243 q = isl_qpolynomial_add(q, isl_qpolynomial_copy(r));
244 }
245
246 if (isl_qpolynomial_is_zero(q))
247 sgn = isl_qpolynomial_sign(set, r);
248 else if (isl_qpolynomial_is_zero(r))
249 sgn = isl_qpolynomial_sign(set, q);
250 else {
251 int sgn_q, sgn_r;
252 sgn_r = isl_qpolynomial_sign(set, r);
253 sgn_q = isl_qpolynomial_sign(set, q);
254 if (sgn_r == sgn_q)
255 sgn = sgn_r;
256 }
257
258 isl_qpolynomial_free(min);
259 isl_qpolynomial_free(base);
260 isl_qpolynomial_free(q);
261 isl_qpolynomial_free(r);
262 }
263
264 isl_int_clear(l);
265
266 isl_vec_free(v);
267
268 return sgn;
269 }
270
271 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold_on_domain(
272 __isl_keep isl_set *set,
273 __isl_take isl_qpolynomial_fold *fold1,
274 __isl_take isl_qpolynomial_fold *fold2)
275 {
276 int i, j;
277 int n1;
278 struct isl_qpolynomial_fold *res = NULL;
279 int better;
280
281 if (!fold1 || !fold2)
282 goto error;
283
284 isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error);
285 isl_assert(fold1->dim->ctx, isl_dim_equal(fold1->dim, fold2->dim),
286 goto error);
287
288 better = fold1->type == isl_fold_max ? -1 : 1;
289
290 if (isl_qpolynomial_fold_is_empty(fold1)) {
291 isl_qpolynomial_fold_free(fold1);
292 return fold2;
293 }
294
295 if (isl_qpolynomial_fold_is_empty(fold2)) {
296 isl_qpolynomial_fold_free(fold2);
297 return fold1;
298 }
299
300 res = qpolynomial_fold_alloc(fold1->type, isl_dim_copy(fold1->dim),
301 fold1->n + fold2->n);
302 if (!res)
303 goto error;
304
305 for (i = 0; i < fold1->n; ++i) {
306 res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]);
307 if (!res->qp[res->n])
308 goto error;
309 res->n++;
310 }
311 n1 = res->n;
312
313 for (i = 0; i < fold2->n; ++i) {
314 for (j = n1 - 1; j >= 0; --j) {
315 isl_qpolynomial *d;
316 int sgn;
317 d = isl_qpolynomial_sub(
318 isl_qpolynomial_copy(res->qp[j]),
319 isl_qpolynomial_copy(fold2->qp[i]));
320 sgn = isl_qpolynomial_sign(set, d);
321 isl_qpolynomial_free(d);
322 if (sgn == 0)
323 continue;
324 if (sgn != better)
325 break;
326 isl_qpolynomial_free(res->qp[j]);
327 if (j != n1 - 1)
328 res->qp[j] = res->qp[n1 - 1];
329 n1--;
330 if (n1 != res->n - 1)
331 res->qp[n1] = res->qp[res->n - 1];
332 res->n--;
333 }
334 if (j >= 0)
335 continue;
336 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
337 if (!res->qp[res->n])
338 goto error;
339 res->n++;
340 }
341
342 isl_qpolynomial_fold_free(fold1);
343 isl_qpolynomial_fold_free(fold2);
344
345 return res;
346 error:
347 isl_qpolynomial_fold_free(res);
348 isl_qpolynomial_fold_free(fold1);
349 isl_qpolynomial_fold_free(fold2);
350 return NULL;
351 }
352
353 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_add_qpolynomial(
354 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_qpolynomial *qp)
355 {
356 int i;
357
358 if (!fold || !qp)
359 goto error;
360
361 if (isl_qpolynomial_is_zero(qp)) {
362 isl_qpolynomial_free(qp);
363 return fold;
364 }
365
366 fold = isl_qpolynomial_fold_cow(fold);
367 if (!fold)
368 goto error;
369
370 for (i = 0; i < fold->n; ++i) {
371 fold->qp[i] = isl_qpolynomial_add(fold->qp[i],
372 isl_qpolynomial_copy(qp));
373 if (!fold->qp[i])
374 goto error;
375 }
376
377 isl_qpolynomial_free(qp);
378 return fold;
379 error:
380 isl_qpolynomial_fold_free(fold);
381 isl_qpolynomial_free(qp);
382 return NULL;
383 }
384
385 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_add_on_domain(
386 __isl_keep isl_set *dom,
387 __isl_take isl_qpolynomial_fold *fold1,
388 __isl_take isl_qpolynomial_fold *fold2)
389 {
390 int i;
391 isl_qpolynomial_fold *res = NULL;
392
393 if (!fold1 || !fold2)
394 goto error;
395
396 if (isl_qpolynomial_fold_is_empty(fold1)) {
397 isl_qpolynomial_fold_free(fold1);
398 return fold2;
399 }
400
401 if (isl_qpolynomial_fold_is_empty(fold2)) {
402 isl_qpolynomial_fold_free(fold2);
403 return fold1;
404 }
405
406 if (fold1->n == 1 && fold2->n != 1)
407 return isl_qpolynomial_fold_add_on_domain(dom, fold2, fold1);
408
409 if (fold2->n == 1) {
410 res = isl_qpolynomial_fold_add_qpolynomial(fold1,
411 isl_qpolynomial_copy(fold2->qp[0]));
412 isl_qpolynomial_fold_free(fold2);
413 return res;
414 }
415
416 res = isl_qpolynomial_fold_add_qpolynomial(
417 isl_qpolynomial_fold_copy(fold1),
418 isl_qpolynomial_copy(fold2->qp[0]));
419
420 for (i = 1; i < fold2->n; ++i) {
421 isl_qpolynomial_fold *res_i;
422 res_i = isl_qpolynomial_fold_add_qpolynomial(
423 isl_qpolynomial_fold_copy(fold1),
424 isl_qpolynomial_copy(fold2->qp[i]));
425 res = isl_qpolynomial_fold_fold_on_domain(dom, res, res_i);
426 }
427
428 isl_qpolynomial_fold_free(fold1);
429 isl_qpolynomial_fold_free(fold2);
430 return res;
431 error:
432 isl_qpolynomial_fold_free(res);
433 isl_qpolynomial_fold_free(fold1);
434 isl_qpolynomial_fold_free(fold2);
435 return NULL;
436 }
437
438 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute_equalities(
439 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_basic_set *eq)
440 {
441 int i;
442
443 if (!fold || !eq)
444 goto error;
445
446 fold = isl_qpolynomial_fold_cow(fold);
447 if (!fold)
448 return NULL;
449
450 for (i = 0; i < fold->n; ++i) {
451 fold->qp[i] = isl_qpolynomial_substitute_equalities(fold->qp[i],
452 isl_basic_set_copy(eq));
453 if (!fold->qp[i])
454 goto error;
455 }
456
457 isl_basic_set_free(eq);
458 return fold;
459 error:
460 isl_basic_set_free(eq);
461 isl_qpolynomial_fold_free(fold);
462 return NULL;
463 }
464
465 #undef PW
466 #define PW isl_pw_qpolynomial_fold
467 #undef EL
468 #define EL isl_qpolynomial_fold
469 #undef IS_ZERO
470 #define IS_ZERO is_empty
471 #undef FIELD
472 #define FIELD fold
473
474 #include <isl_pw_templ.c>
475
476 #undef UNION
477 #define UNION isl_union_pw_qpolynomial_fold
478 #undef PART
479 #define PART isl_pw_qpolynomial_fold
480 #undef PARTS
481 #define PARTS pw_qpolynomial_fold
482
483 #include <isl_union_templ.c>
484
485 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_empty(enum isl_fold type,
486 __isl_take isl_dim *dim)
487 {
488 return qpolynomial_fold_alloc(type, dim, 0);
489 }
490
491 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_alloc(
492 enum isl_fold type, __isl_take isl_qpolynomial *qp)
493 {
494 isl_qpolynomial_fold *fold;
495
496 if (!qp)
497 return NULL;
498
499 fold = qpolynomial_fold_alloc(type, isl_dim_copy(qp->dim), 1);
500 if (!fold)
501 goto error;
502
503 fold->qp[0] = qp;
504 fold->n++;
505
506 return fold;
507 error:
508 isl_qpolynomial_fold_free(fold);
509 isl_qpolynomial_free(qp);
510 return NULL;
511 }
512
513 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_copy(
514 __isl_keep isl_qpolynomial_fold *fold)
515 {
516 if (!fold)
517 return NULL;
518
519 fold->ref++;
520 return fold;
521 }
522
523 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_dup(
524 __isl_keep isl_qpolynomial_fold *fold)
525 {
526 int i;
527 isl_qpolynomial_fold *dup;
528
529 if (!fold)
530 return NULL;
531 dup = qpolynomial_fold_alloc(fold->type,
532 isl_dim_copy(fold->dim), fold->n);
533 if (!dup)
534 return NULL;
535
536 dup->n = fold->n;
537 for (i = 0; i < fold->n; ++i) {
538 dup->qp[i] = isl_qpolynomial_copy(fold->qp[i]);
539 if (!dup->qp[i])
540 goto error;
541 }
542
543 return dup;
544 error:
545 isl_qpolynomial_fold_free(dup);
546 return NULL;
547 }
548
549 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_cow(
550 __isl_take isl_qpolynomial_fold *fold)
551 {
552 if (!fold)
553 return NULL;
554
555 if (fold->ref == 1)
556 return fold;
557 fold->ref--;
558 return isl_qpolynomial_fold_dup(fold);
559 }
560
561 void isl_qpolynomial_fold_free(__isl_take isl_qpolynomial_fold *fold)
562 {
563 int i;
564
565 if (!fold)
566 return;
567 if (--fold->ref > 0)
568 return;
569
570 for (i = 0; i < fold->n; ++i)
571 isl_qpolynomial_free(fold->qp[i]);
572 isl_dim_free(fold->dim);
573 free(fold);
574 }
575
576 int isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold *fold)
577 {
578 if (!fold)
579 return -1;
580
581 return fold->n == 0;
582 }
583
584 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold(
585 __isl_take isl_qpolynomial_fold *fold1,
586 __isl_take isl_qpolynomial_fold *fold2)
587 {
588 int i;
589 struct isl_qpolynomial_fold *res = NULL;
590
591 if (!fold1 || !fold2)
592 goto error;
593
594 isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error);
595 isl_assert(fold1->dim->ctx, isl_dim_equal(fold1->dim, fold2->dim),
596 goto error);
597
598 if (isl_qpolynomial_fold_is_empty(fold1)) {
599 isl_qpolynomial_fold_free(fold1);
600 return fold2;
601 }
602
603 if (isl_qpolynomial_fold_is_empty(fold2)) {
604 isl_qpolynomial_fold_free(fold2);
605 return fold1;
606 }
607
608 res = qpolynomial_fold_alloc(fold1->type, isl_dim_copy(fold1->dim),
609 fold1->n + fold2->n);
610 if (!res)
611 goto error;
612
613 for (i = 0; i < fold1->n; ++i) {
614 res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]);
615 if (!res->qp[res->n])
616 goto error;
617 res->n++;
618 }
619
620 for (i = 0; i < fold2->n; ++i) {
621 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
622 if (!res->qp[res->n])
623 goto error;
624 res->n++;
625 }
626
627 isl_qpolynomial_fold_free(fold1);
628 isl_qpolynomial_fold_free(fold2);
629
630 return res;
631 error:
632 isl_qpolynomial_fold_free(res);
633 isl_qpolynomial_fold_free(fold1);
634 isl_qpolynomial_fold_free(fold2);
635 return NULL;
636 }
637
638 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_fold(
639 __isl_take isl_pw_qpolynomial_fold *pw1,
640 __isl_take isl_pw_qpolynomial_fold *pw2)
641 {
642 int i, j, n;
643 struct isl_pw_qpolynomial_fold *res;
644 isl_set *set;
645
646 if (!pw1 || !pw2)
647 goto error;
648
649 isl_assert(pw1->dim->ctx, isl_dim_equal(pw1->dim, pw2->dim), goto error);
650
651 if (isl_pw_qpolynomial_fold_is_zero(pw1)) {
652 isl_pw_qpolynomial_fold_free(pw1);
653 return pw2;
654 }
655
656 if (isl_pw_qpolynomial_fold_is_zero(pw2)) {
657 isl_pw_qpolynomial_fold_free(pw2);
658 return pw1;
659 }
660
661 n = (pw1->n + 1) * (pw2->n + 1);
662 res = isl_pw_qpolynomial_fold_alloc_(isl_dim_copy(pw1->dim), n);
663
664 for (i = 0; i < pw1->n; ++i) {
665 set = isl_set_copy(pw1->p[i].set);
666 for (j = 0; j < pw2->n; ++j) {
667 struct isl_set *common;
668 isl_qpolynomial_fold *sum;
669 set = isl_set_subtract(set,
670 isl_set_copy(pw2->p[j].set));
671 common = isl_set_intersect(isl_set_copy(pw1->p[i].set),
672 isl_set_copy(pw2->p[j].set));
673 if (isl_set_fast_is_empty(common)) {
674 isl_set_free(common);
675 continue;
676 }
677
678 sum = isl_qpolynomial_fold_fold_on_domain(common,
679 isl_qpolynomial_fold_copy(pw1->p[i].fold),
680 isl_qpolynomial_fold_copy(pw2->p[j].fold));
681
682 res = isl_pw_qpolynomial_fold_add_piece(res, common, sum);
683 }
684 res = isl_pw_qpolynomial_fold_add_piece(res, set,
685 isl_qpolynomial_fold_copy(pw1->p[i].fold));
686 }
687
688 for (j = 0; j < pw2->n; ++j) {
689 set = isl_set_copy(pw2->p[j].set);
690 for (i = 0; i < pw1->n; ++i)
691 set = isl_set_subtract(set, isl_set_copy(pw1->p[i].set));
692 res = isl_pw_qpolynomial_fold_add_piece(res, set,
693 isl_qpolynomial_fold_copy(pw2->p[j].fold));
694 }
695
696 isl_pw_qpolynomial_fold_free(pw1);
697 isl_pw_qpolynomial_fold_free(pw2);
698
699 return res;
700 error:
701 isl_pw_qpolynomial_fold_free(pw1);
702 isl_pw_qpolynomial_fold_free(pw2);
703 return NULL;
704 }
705
706 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
707 __isl_take isl_union_pw_qpolynomial_fold *u,
708 __isl_take isl_pw_qpolynomial_fold *part)
709 {
710 uint32_t hash;
711 struct isl_hash_table_entry *entry;
712
713 u = isl_union_pw_qpolynomial_fold_cow(u);
714
715 if (!part || !u)
716 goto error;
717
718 isl_assert(u->dim->ctx, isl_dim_match(part->dim, isl_dim_param, u->dim,
719 isl_dim_param), goto error);
720
721 hash = isl_dim_get_hash(part->dim);
722 entry = isl_hash_table_find(u->dim->ctx, &u->table, hash,
723 &has_dim, part->dim, 1);
724 if (!entry)
725 goto error;
726
727 if (!entry->data)
728 entry->data = part;
729 else {
730 entry->data = isl_pw_qpolynomial_fold_fold(entry->data,
731 isl_pw_qpolynomial_fold_copy(part));
732 if (!entry->data)
733 goto error;
734 isl_pw_qpolynomial_fold_free(part);
735 }
736
737 return u;
738 error:
739 isl_pw_qpolynomial_fold_free(part);
740 isl_union_pw_qpolynomial_fold_free(u);
741 return NULL;
742 }
743
744 static int fold_part(__isl_take isl_pw_qpolynomial_fold *part, void *user)
745 {
746 isl_union_pw_qpolynomial_fold **u;
747 u = (isl_union_pw_qpolynomial_fold **)user;
748
749 *u = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(*u, part);
750
751 return 0;
752 }
753
754 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold(
755 __isl_take isl_union_pw_qpolynomial_fold *u1,
756 __isl_take isl_union_pw_qpolynomial_fold *u2)
757 {
758 u1 = isl_union_pw_qpolynomial_fold_cow(u1);
759
760 if (!u1 || !u2)
761 goto error;
762
763 if (isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(u2,
764 &fold_part, &u1) < 0)
765 goto error;
766
767 isl_union_pw_qpolynomial_fold_free(u2);
768
769 return u1;
770 error:
771 isl_union_pw_qpolynomial_fold_free(u1);
772 isl_union_pw_qpolynomial_fold_free(u2);
773 return NULL;
774 }
775
776 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_from_pw_qpolynomial(
777 enum isl_fold type, __isl_take isl_pw_qpolynomial *pwqp)
778 {
779 int i;
780 isl_pw_qpolynomial_fold *pwf;
781
782 if (!pwqp)
783 return NULL;
784
785 pwf = isl_pw_qpolynomial_fold_alloc_(isl_dim_copy(pwqp->dim), pwqp->n);
786
787 for (i = 0; i < pwqp->n; ++i)
788 pwf = isl_pw_qpolynomial_fold_add_piece(pwf,
789 isl_set_copy(pwqp->p[i].set),
790 isl_qpolynomial_fold_alloc(type,
791 isl_qpolynomial_copy(pwqp->p[i].qp)));
792
793 isl_pw_qpolynomial_free(pwqp);
794
795 return pwf;
796 }
797
798 int isl_qpolynomial_fold_is_equal(__isl_keep isl_qpolynomial_fold *fold1,
799 __isl_keep isl_qpolynomial_fold *fold2)
800 {
801 int i;
802
803 if (!fold1 || !fold2)
804 return -1;
805
806 if (fold1->n != fold2->n)
807 return 0;
808
809 /* We probably want to sort the qps first... */
810 for (i = 0; i < fold1->n; ++i) {
811 int eq = isl_qpolynomial_is_equal(fold1->qp[i], fold2->qp[i]);
812 if (eq < 0 || !eq)
813 return eq;
814 }
815
816 return 1;
817 }
818
819 __isl_give isl_qpolynomial *isl_qpolynomial_fold_eval(
820 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_point *pnt)
821 {
822 isl_qpolynomial *qp;
823
824 if (!fold || !pnt)
825 goto error;
826 isl_assert(pnt->dim->ctx, isl_dim_equal(pnt->dim, fold->dim), goto error);
827 isl_assert(pnt->dim->ctx,
828 fold->type == isl_fold_max || fold->type == isl_fold_min,
829 goto error);
830
831 if (fold->n == 0)
832 qp = isl_qpolynomial_zero(isl_dim_copy(fold->dim));
833 else {
834 int i;
835 qp = isl_qpolynomial_eval(isl_qpolynomial_copy(fold->qp[0]),
836 isl_point_copy(pnt));
837 for (i = 1; i < fold->n; ++i) {
838 isl_qpolynomial *qp_i;
839 qp_i = isl_qpolynomial_eval(
840 isl_qpolynomial_copy(fold->qp[i]),
841 isl_point_copy(pnt));
842 if (fold->type == isl_fold_max)
843 qp = isl_qpolynomial_max_cst(qp, qp_i);
844 else
845 qp = isl_qpolynomial_min_cst(qp, qp_i);
846 }
847 }
848 isl_qpolynomial_fold_free(fold);
849 isl_point_free(pnt);
850
851 return qp;
852 error:
853 isl_qpolynomial_fold_free(fold);
854 isl_point_free(pnt);
855 return NULL;
856 }
857
858 size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold *pwf)
859 {
860 int i;
861 size_t n = 0;
862
863 for (i = 0; i < pwf->n; ++i)
864 n += pwf->p[i].fold->n;
865
866 return n;
867 }
868
869 __isl_give isl_qpolynomial *isl_qpolynomial_fold_opt_on_domain(
870 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *set, int max)
871 {
872 int i;
873 isl_qpolynomial *opt;
874
875 if (!set || !fold)
876 goto error;
877
878 if (fold->n == 0) {
879 isl_dim *dim = isl_dim_copy(fold->dim);
880 isl_set_free(set);
881 isl_qpolynomial_fold_free(fold);
882 return isl_qpolynomial_zero(dim);
883 }
884
885 opt = isl_qpolynomial_opt_on_domain(isl_qpolynomial_copy(fold->qp[0]),
886 isl_set_copy(set), max);
887 for (i = 1; i < fold->n; ++i) {
888 isl_qpolynomial *opt_i;
889 opt_i = isl_qpolynomial_opt_on_domain(
890 isl_qpolynomial_copy(fold->qp[i]),
891 isl_set_copy(set), max);
892 if (max)
893 opt = isl_qpolynomial_max_cst(opt, opt_i);
894 else
895 opt = isl_qpolynomial_min_cst(opt, opt_i);
896 }
897
898 isl_set_free(set);
899 isl_qpolynomial_fold_free(fold);
900
901 return opt;
902 error:
903 isl_set_free(set);
904 isl_qpolynomial_fold_free(fold);
905 return NULL;
906 }
907
908 /* Check whether for each quasi-polynomial in "fold2" there is
909 * a quasi-polynomial in "fold1" that dominates it on "set".
910 */
911 static int qpolynomial_fold_covers_on_domain(__isl_keep isl_set *set,
912 __isl_keep isl_qpolynomial_fold *fold1,
913 __isl_keep isl_qpolynomial_fold *fold2)
914 {
915 int i, j;
916 int covers;
917
918 if (!set || !fold1 || !fold2)
919 return -1;
920
921 covers = fold1->type == isl_fold_max ? 1 : -1;
922
923 for (i = 0; i < fold2->n; ++i) {
924 for (j = 0; j < fold1->n; ++j) {
925 isl_qpolynomial *d;
926 int sgn;
927
928 d = isl_qpolynomial_sub(
929 isl_qpolynomial_copy(fold1->qp[j]),
930 isl_qpolynomial_copy(fold2->qp[i]));
931 sgn = isl_qpolynomial_sign(set, d);
932 isl_qpolynomial_free(d);
933 if (sgn == covers)
934 break;
935 }
936 if (j >= fold1->n)
937 return 0;
938 }
939
940 return 1;
941 }
942
943 /* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains
944 * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates
945 * that of pwf2.
946 */
947 int isl_pw_qpolynomial_fold_covers(__isl_keep isl_pw_qpolynomial_fold *pwf1,
948 __isl_keep isl_pw_qpolynomial_fold *pwf2)
949 {
950 int i, j;
951 isl_set *dom1, *dom2;
952 int is_subset;
953
954 if (!pwf1 || !pwf2)
955 return -1;
956
957 if (pwf2->n == 0)
958 return 1;
959 if (pwf1->n == 0)
960 return 0;
961
962 dom1 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1));
963 dom2 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2));
964 is_subset = isl_set_is_subset(dom2, dom1);
965 isl_set_free(dom1);
966 isl_set_free(dom2);
967
968 if (is_subset < 0 || !is_subset)
969 return is_subset;
970
971 for (i = 0; i < pwf2->n; ++i) {
972 for (j = 0; j < pwf1->n; ++j) {
973 int is_empty;
974 isl_set *common;
975 int covers;
976
977 common = isl_set_intersect(isl_set_copy(pwf1->p[j].set),
978 isl_set_copy(pwf2->p[i].set));
979 is_empty = isl_set_is_empty(common);
980 if (is_empty < 0 || is_empty) {
981 isl_set_free(common);
982 if (is_empty < 0)
983 return -1;
984 continue;
985 }
986 covers = qpolynomial_fold_covers_on_domain(common,
987 pwf1->p[j].fold, pwf2->p[i].fold);
988 isl_set_free(common);
989 if (covers < 0 || !covers)
990 return covers;
991 }
992 }
993
994 return 1;
995 }
996
997 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_morph(
998 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_morph *morph)
999 {
1000 int i;
1001 isl_ctx *ctx;
1002
1003 if (!fold || !morph)
1004 goto error;
1005
1006 ctx = fold->dim->ctx;
1007 isl_assert(ctx, isl_dim_equal(fold->dim, morph->dom->dim), goto error);
1008
1009 fold = isl_qpolynomial_fold_cow(fold);
1010 if (!fold)
1011 goto error;
1012
1013 isl_dim_free(fold->dim);
1014 fold->dim = isl_dim_copy(morph->ran->dim);
1015 if (!fold->dim)
1016 goto error;
1017
1018 for (i = 0; i < fold->n; ++i) {
1019 fold->qp[i] = isl_qpolynomial_morph(fold->qp[i],
1020 isl_morph_copy(morph));
1021 if (!fold->qp[i])
1022 goto error;
1023 }
1024
1025 isl_morph_free(morph);
1026
1027 return fold;
1028 error:
1029 isl_qpolynomial_fold_free(fold);
1030 isl_morph_free(morph);
1031 return NULL;
1032 }
1033
1034 enum isl_fold isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold *fold)
1035 {
1036 if (!fold)
1037 return isl_fold_list;
1038 return fold->type;
1039 }
1040
1041 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_lift(
1042 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_dim *dim)
1043 {
1044 int i;
1045 isl_ctx *ctx;
1046
1047 if (!fold || !dim)
1048 goto error;
1049
1050 if (isl_dim_equal(fold->dim, dim)) {
1051 isl_dim_free(dim);
1052 return fold;
1053 }
1054
1055 fold = isl_qpolynomial_fold_cow(fold);
1056 if (!fold)
1057 goto error;
1058
1059 isl_dim_free(fold->dim);
1060 fold->dim = isl_dim_copy(dim);
1061 if (!fold->dim)
1062 goto error;
1063
1064 for (i = 0; i < fold->n; ++i) {
1065 fold->qp[i] = isl_qpolynomial_lift(fold->qp[i],
1066 isl_dim_copy(dim));
1067 if (!fold->qp[i])
1068 goto error;
1069 }
1070
1071 isl_dim_free(dim);
1072
1073 return fold;
1074 error:
1075 isl_qpolynomial_fold_free(fold);
1076 isl_dim_free(dim);
1077 return NULL;
1078 }
1079
1080 int isl_qpolynomial_fold_foreach_qpolynomial(
1081 __isl_keep isl_qpolynomial_fold *fold,
1082 int (*fn)(__isl_take isl_qpolynomial *qp, void *user), void *user)
1083 {
1084 int i;
1085
1086 if (!fold)
1087 return -1;
1088
1089 for (i = 0; i < fold->n; ++i)
1090 if (fn(isl_qpolynomial_copy(fold->qp[i]), user) < 0)
1091 return -1;
1092
1093 return 0;
1094 }
1095
1096 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_move_dims(
1097 __isl_take isl_qpolynomial_fold *fold,
1098 enum isl_dim_type dst_type, unsigned dst_pos,
1099 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1100 {
1101 int i;
1102
1103 if (n == 0)
1104 return fold;
1105
1106 fold = isl_qpolynomial_fold_cow(fold);
1107 if (!fold)
1108 return NULL;
1109
1110 fold->dim = isl_dim_move(fold->dim, dst_type, dst_pos,
1111 src_type, src_pos, n);
1112 if (!fold->dim)
1113 goto error;
1114
1115 for (i = 0; i < fold->n; ++i) {
1116 fold->qp[i] = isl_qpolynomial_move_dims(fold->qp[i],
1117 dst_type, dst_pos, src_type, src_pos, n);
1118 if (!fold->qp[i])
1119 goto error;
1120 }
1121
1122 return fold;
1123 error:
1124 isl_qpolynomial_fold_free(fold);
1125 return NULL;
1126 }
1127
1128 /* For each 0 <= i < "n", replace variable "first" + i of type "type"
1129 * in fold->qp[k] by subs[i].
1130 */
1131 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute(
1132 __isl_take isl_qpolynomial_fold *fold,
1133 enum isl_dim_type type, unsigned first, unsigned n,
1134 __isl_keep isl_qpolynomial **subs)
1135 {
1136 int i;
1137
1138 if (n == 0)
1139 return fold;
1140
1141 fold = isl_qpolynomial_fold_cow(fold);
1142 if (!fold)
1143 return NULL;
1144
1145 for (i = 0; i < fold->n; ++i) {
1146 fold->qp[i] = isl_qpolynomial_substitute(fold->qp[i],
1147 type, first, n, subs);
1148 if (!fold->qp[i])
1149 goto error;
1150 }
1151
1152 return fold;
1153 error:
1154 isl_qpolynomial_fold_free(fold);
1155 return NULL;
1156 }
Integer set library