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