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